OperatorPrecedenceHack - Software Development
 OperatorPrecedenceHack UserPreferences

# 1. Operator Precedence by Macro Expansion!

If you're looking for for a serious algorithm, have a look at OperatorPrecedence; otherwise read on. This is to some extent a joke algorithm, but it does actually work and in some cases might prove useful as a quick hack. I learned this fom Jeff Tansley when he was a lecturer at Edinburgh University. I'm not sure where he got it from but it has been passed around from hacker to hacker for years, without ever being taken seriously enough to end up in print anywhere.

Let's assume that you have an expression parser which works, but assumes left to right associativity and does not understand operator precedence. This will allow you to trivially add parentheses to that expression so that it is fully parenthesised and therefore correctly reflects operator precedence. You can just about implement this with a macro-processor, even, or a trivial filter on input.

First, write down your operators in order of precedence:

```^
* /
+ -
```

Now, redefine each operator as a number of closing parentheses followed by the original operator followed by the same number of opening parentheses. The highest priority operator gets one level of parentheses, and subsequent levels get more, respectively:

```^        ") ^ ("
* /     ")) * (("   and   ")) / (("
+ -    "))) + ((("  and  "))) - ((("
```

Here's the algorithm:

Before you copy any items from the input to the output, print a number of opening parentheses which is one larger than the largest string above i.e. "(((("

Take your input expression string one item at a time, from left to right.

For each item, if it is a terminal (eg a variable or a constant) just output it; if it is an operator, output the replacement string above.

Finally, output a matching set of closing parentheses, i.e. "))))".

Let's take a test string, and apply this algorithm:

```a*b+c^d/e
```

First to be output is the enclosing parentheses and the first token:

```((((a
```

Next is "*" which is replaced by ")) * ((", followed by the next token:

```((((a)) * ((b
```

repeat for all remaining tokens...

```((((a)) * ((b))) + (((c) ^ (d)) / ((e
```

and finally after the last token, the closing "))))" ...

```((((a)) * ((b))) + (((c) ^ (d)) / ((e))))
```

Now if you parse this with a simple grammar, you'll find it correctly reflects operator precedence!

We can check this by manually removing redundant parentheses:

```((((a)) * ((b))) + (((c) ^ (d)) / ((e))))
((( a ) * ( b )) + (( c  ^  d ) / ( e )))
((  a   *   b  ) + (( c  ^  d ) /   e  ))
(  a   *   b  ) + (( c  ^  d ) /   e  )
```

i.e. the final expression is "(a*b) + ((c^d)/e)" which is indeed correct. The fully-parenthesised expression can be trivially parsed by a recursive descent parser.

This algorithm is congruent with Dijkstra's "shunting yard" operator precedence algorithm; copying a "(" to the output before a terminal is equivalent to switching the tracks so that the next item is pushed on the stack, and outputting a ")" is the same as popping off the stack.

Here is some C code to parenthesise (but not evaluate) an expression:

```#include <stdio.h>
char *intable[] = { NULL, "^", "*", "/", "+", "-", "" };
char *outtable[] = { "))))\n", ")^(", "))*((", "))/((", ")))+(((", ")))-(((", "((((" };
int main(int argc, char **argv)
{
int i, tab;
for (argv[i=0]=""; i <= argc; i++) {
for (tab = 0; tab < (sizeof(outtable)/sizeof(char *)); tab += 1) {
if ((!argv[i]) || (tab && !strcmp(argv[i], intable[tab]))) {
printf("%s", outtable[tab]); break;
} else if (tab && !*intable[tab]) printf("%s", argv[i]);
}
}
}
```

invoke it as:

```\$ cc -o parenthesise parenthesise.c
\$ ./parenthesise a \* b + c ^ d / e
((((a))*((b)))+(((c)^(d))/((e))))
```

Actually a good language in which to implement this algorithm would be "Wonderpop", a derivation of "Pop2" which treats the input data stream (the equivalent of C's stdin) as a list which can be manipulated, making it trivially easy to apply pipe-like filters to the data that you read.

# 2. UPDATE

I hacked up a CPP-like filter, which is probably good enough to be used in projects that don't need the full complexity of CPP, using this algorithm just for the fun of it. Source is online.

In the code above where I said "The fully-parenthesised expression can be trivially parsed by a recursive descent parser.", that was actually overkill. The 'parser' in the program referenced above is actually a trivial Left-to-right scan, noting the position of the previous '(' in a linked list every time it passes one. This is a trick I stole from Hamish Dewar's "Ecce" editor, which parses a parenthesised command language the same way. (I think in hindsight it is probably the degenerate case of a shift-reduce parser.)

## 2.1. Algorithm flaw corrected!

After implementing the code above, I discovered that the algorithm as described does not work if the expression passed to it already contains parentheses! However this turns out to be trivial to correct: when you pass a '(' symbol through the LR stream, macro expand it to "((((" instead! Similarly for ')'. It works.

# 3. The Last Word

I extracted the operator precedence code from the filter I mentioned above, and turned it into a stand-alone expression evaluator. It's actually a better piece of code than either of the above, and I'll move it to this wiki page when I get a chance...