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.

Conversion from Infix to Prefix using Stack:

The algorithm is as follows:

1. Do a horizontal mirror reflection to the Infix expression first.
2. Now from left to right extract every element and do perform exactly the Infix to Postfix conversion.
3. The result after a while is a Postfix form of the mirrored expression.
4. Finally recalling that the expression was mirrored in step 1, do again another horizontal mirror reflection to the obtained Postfix expression. The final result is corresponding Prefix form of the original Infix expression.

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

First we do horizontal mirror reflection and we get: F / E - D % C * B + A

Once again we do horizontal mirror reflection and we get our result as: + A - * B % C D / E F

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

First we do horizontal mirror reflection and we get: ( F / E - D % C ) * B + A

Once again we do horizontal mirror reflection and we get our result as: + * B - % C D / E F

Evaluation of Postfix expression using Stack:

The algorithm is as follows:

1. Create a stack to store operands continuously.
2. PUSH every operand in to the stack as it is encountered from left to right.
3. If an operator is encountered, it will not be PUSHed, instead, it will be performrd over two continuous TOS elements.
4. Repeat the steps till the end of expression.

Ex.01 - Solve the Postfix expression    5 6 + 4 3 + *     using stack.