Expression (Postfix, Prefix, Infix) conversion

Arithmetic expression evaluation

In expression (A + B) * C, the addition of A and B to be done first before the multiplication. Infix requires the parentheses to force the performance of the addition before the multiplication. However, when A + B was written in prefix, the addition operator was simply moved before the operands, + A B. The result of this operation becomes the first operand for the multiplication. The multiplication operator is moved in front of the entire expression, giving us * + A B C. Likewise, in postfix A B + forces the addition to happen first. The multiplication can be done to that result and the remaining operand C. Postfix expression is then A B + C *.

Balancing Parentheses

Stack is used to read an arithmetic expression and determine whether or not the parentheses in the expression are correctly matched. Here is an algorithm for solving this problem.

• Scan the tokens from left to right ignoring everything but open parenthesis and close parenthesis tokens.
• Whenever you encounter an open parenthesis token, push it on the stack. Whenever you encounter a close parenthesis token, pop the stack. If the stack is empty, output an error message.
• When you have read all the tokens, check to see whether or not the stack is empty. If the stack is empty, declare success. If the stack still has something on it you have an unbalanced open parenthesis in your expression.

Postfix expression

A postfix expression is a collection of operators and operands in which the operator is placed after the operands. Infix expression to Postfix expression

1. Read all the symbols one by one from left to right in the given Infix Expression.
2. If the reading symbol is operand, then directly print it to the result (Output).
3. If the reading symbol is left parenthesis ‘(‘, then push it on to the Stack.
4. If the reading symbol is right parenthesis ‘)’, then pop all the contents of stack until respective left parenthesis is poped and print each poped symbol to the result.
5. If the reading symbol is operator (+ , – , * , / etc.,), then push it on to the Stack. However, first pop the operators which are already on the stack that have higher or equal precedence than current operator and print them to the result.

Example: 
Convert A * (B + C) * D to postfix notation. 

Move  Token    Stack     Output 
1       A      Empty       A
2       *        *         A
3       (       (*         A
4       B       (*         A B
5       +      +(*         A B
6       C      +(*         A B C
7       )        *         A B C +
8       *        *         A B C + *
9       D        *         A B C + * D
10             Empty

Postfix Expression Evaluation

1. Read all the symbols one by one from left to right in the given Postfix Expression
2. If the reading symbol is operand, then push it on to the Stack.
3. If the reading symbol is operator (+ , – , * , / etc.,), then perform two pop operations and store the two popped operands in two different variables (operand1 and operand2). Then perform reading symbol operation using operand1 and operand2 and push result back on to the Stack.
4. Finally perform a pop operation and display the popped value as final result.

Infix expression evaluation

Given values of the operand A, B, C and D, the problem is to evaluate an expression of the form: A+B*C-D. We will use two stacks:
Operand stack: to keep values (numbers)
Operator stack: to keep operators (+, -, *, . and ^).

In the following, “process” means

• pop operand stack once (value1)
• pop operator stack once (operator)
• pop operand stack again (value2)
• compute value1 operator  value2
• push the value obtained in operand stack.

Algorithm:

1. If the character is an operand, push it onto the operand stack.
2. If the character is an operator, and the operator stack is empty then push it onto the operator stack.
3. If the character is an operator and the operator stack is not empty, and the character’s precedence is greater than the precedence of the stack top of operator stack, then push the character onto the operator stack.
4. If the character is “(“, then push it onto operator stack.
5. If the character is “)”, then “process” as explained above until the corresponding “(” is encountered in operator stack.  At this stage POP the operator stack and ignore “(.”
6. If cases (a), (b), (c), (d) and (e) do not apply, then process as explained above.

When there are no more input characters, keep processing until the operator stack becomes empty.  The values left in the operand stack is the final result of the expression.

Reference :-

Evaluation of infix expressions