Conversion to Reverse Polish Notation (RPN) of expressions:
In the RPN, the arguments have to be put on an operand stack before the call to the operator or function. For this, we use a stack for the operators, and the following algorithm:
- if an argument is found (constant value or variable), the code to put the argument value onto the operand stack is generated (the operand is passed straight through to the output).
- if an operator or function is found, get the operators/functions with higher or equal priority off the operator stack (in LIFO order) and send them to the output (generate call to them in the output code), and put that operator onto the operator stack.
at the end, empty the operator stack and put the operators to the output.
In our case we used two lists of operators or functions.
For an arithmetic expressions, in order of decreasing priority, functions, multiplications & divisions, additions & subtractions, values assignment operator to a variable.
for a boolean expression, another value assignment operator, (that first duplicates the last value on the operand stack, takes one to store it into the variables table, and leaves the second for the comparison operation), the arithmetic comparison operators ( > >= < <= == !=), and the boolean combination operator and followed by the or, xor that have lowest priority.
That way following expression is possible:
if (x == var = a+b/c)
A trick is used for the expression between (): the parentheses are defined as operators with the lowest priority. If a '(' is found, it is put onto the operators stack. Then the expression between the () is parsed normally, the opening '(' operator remaining on the stack as its priority is the lowest. When reaching the closing ')', all operators with strictly higher priority are taken from the operators stack. So the whole expression between () has been converted, just the opening '(' has to be suppressed from the stack. We can't empty those with equal priority than the parenthese operator, because if we have an expression with embedded parentheses as + ((, on finding the first closing ), both parentheses would be taken from the operators stack, and the conversion to RPN would fail.