Question

Using a stack, write a program that turns a simple infix arithmetic expression into a postfix expression. For example, 1 + 2 * 3 becomes 2 3 * 1 +. Also, evaluate the expression to ensure the expression is correct.

Answer 1

Push "("onto Stack, and add ")" to the end of X.

Scan X from left to right and repeat Step 3 to 6 for each element of X until the Stack is empty.

If an operand is encountered, add it to Y.

If a left parenthesis is encountered, push it onto Stack.

If an operator is encountered ,then:

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.

Add operator to Stack.

[End of If]

If a right parenthesis is encountered ,then:

Repeatedly pop from Stack and add to Y each operator (on the top of Stack) until a left parenthesis is encountered.

Remove the left Parenthesis.

[End of If]

[End of If]

END.

Complexity of algorithm in both worst and best case is O(n^2), as expression is iterated two times simultaneously, firstly for scanning the infix expression and secondly while poping out of stack.

Eg : a + b - d

* As in above Infix expression, O(n) will be the complexity for scanning each literal, while at the same time we pop the literals from stack, hence the complexity of algorithm is O(n*n) i.e : O(n^2).

For storing Infix expression of n literals the space complexity is O(n) and for stack to hold atmost n literals the space complexity is O(n), hence

* Total space complexity is O(n+n) = O(2n) i.e : O(n)

Given that:

1+2*3

The post fix expression is

1 2 3 * +