HackerRank Stack Quiz-2

Postfix expression requires that its operators come after the corresponding operands.

Prefix expression notation requires that all operators precede the two operands that they work on.

When a left parenthesis is occured, it is placed on to the operator stack. When the corresponding right parenthesis is encountered, then the stack is popped until the left parenthesis and removes both the parenthesis.

 

The mathematically calculated time complexity of an infix to postfix conversion algorithm is O(n).

abc*+de*+

The postfix expression for the given expression is found to be abcd^e-fgh*+^*+i- when we use postfix conversion algorithms.

 

The prefix expression for the given expression is found to be((1+2)/(4/2))*(3+5)  then, (3/2)*8 and gives 12.

One Stack is enough for evaluating expressions to prefix into postfix or infix and vice-versa.

Postfix notation to infix notation is easier to implement.

Given postfix expression : 4 2 + 3 * 4 5 * –

⇒ (4 + 2) 3 * 4 5 * -

⇒ ((4 + 2) * 3) 4 5 * -

⇒ ((4 + 2) * 3) (4 * 5) -

⇒ ((4 + 2) * 3) - (4 * 5)

So, the equivalent infix expression is (4 + 2) * 3 - (4 * 5) and it’s value is -2.