Question

java

1. Convert the following Infix expression to a Postfix expression. Show all work

                           Infix Expression                                                 Stack                             Postfix Expression

----------------------------------------------------------------------------------------------------------------------------

8 - 9*(2 + 1/4) + 3*7                                                     (empty)                            (blank)

2. Evaluate the following Postfix expression. Once again, show all work.

           Postfix                                               Stack                     Result

          ---------------------------------------    --------------------    --------------

           2 7 + 12 4 / * 8 5 + -

Answer 1

Infix to Postfix expression algorithm

Let, X is an arithmetic expression written in infix notation. This algorithm finds the equivalent postfix expression Y.

1. Push “(“onto Stack, and add “)” to the end of X.
2. Scan X from left to right and repeat Step 3 to 6 for each element of X until the Stack is empty.
3. If an operand is encountered, add it to Y.
4. If a left parenthesis is encountered, push it onto Stack.
5. If an operator is encountered ,then:
   1. Repeatedly pop from Stack and add to Y each operator (on the top of Stack) which has the same precedence as or higher precedence than operator.
   2. Add operator to Stack.
      [End of If]
6. If a right parenthesis is encountered ,then:
   1. Repeatedly pop from Stack and add to Y each operator (on the top of Stack) until a left parenthesis is encountered.
   2. Remove the left Parenthesis.
      [End of If]
      [End of If]
7. END.

Postfix Evaluation algorithm

1) Add ) to postfix expression.
2) Read postfix expression Left to Right until ) encountered
3) If operand is encountered, push it onto Stack
[End If]
4) If operator is encountered, Pop two elements
i) A -> Top element
ii) B-> Next to Top element
iii) Evaluate B operator A
push B operator A onto Stack
5) Set result = pop
6) END