Handling of arithmetic expressions using Stack

---

Mathematical Notations:

Polish mathematician Lukasiewicz was the first to propose that the arithmatic expressions can be written in some different ways as well. His proposals were: Prefix and Postfix. Prefix was later known as Polish and post fix was known as Reverse-Polish. Note that the conventional notation is known as Infix.

The detailing of arithmatic notations are as follows:

• Infix

The operator resides in between two adjacent operands. This in in accordance that an entire expression (if in bracket), is an like an operand. Ex: A + B

• Prefix

The operator resides immediately before the two continuous operands. Ex: + A B

• Postfix

The operator resides immediately after two continuous operands. Ex: A B +

Conversion from Infix to Postfix using Stack:

The translation works in a specific manner. We use two registers and a stack here. The registers are to store infix and postfix expressions respectively while the stack for storing operators as encountered during translation. The detailed algorithm is as follows:

1. Store the infix expression in register R1 and use R2 for storing postfix notation as we build it.
2. From Left to Right, extract an element of R1 and do the following:
1. If it is an operand, append it into the register R2.
2. Else if it is an operator, do the following:
1. If the stack is empty, PUSH it onto the stack.
2. Else if the precedence of this operator is higher than the operator on TOS, PUSH it on to the stack.
3. Else if the precedence of this operator is lower than the operator on TOS, POP the TOS, append in R2 and goto step b.
4. Else if the precedence of this operator is equal to the TOS, POP the TOS append in R2 and goto step b.
3. Else if it is an opening paranthesis PUSH it on to the stack, start a new stack hierarchy untill an closing paranthesis is found and goto step 2.
4. Else if it is a closing paranthesis, POP every operator on stack untill the opening paranthesis is found.
5. Else if reached on End of Expression, POP every operator remaining on the stack and append in R2.
3. End of algorithm.

Ex.01 - Convert the expression A + B * C % D - E / F in to corresponding postfix notation.

Ex.02 - Convert the expression A + B * (C % D - E / F) in to corresponding postfix notation.