PadhaikoAll subjects

Past exam question: 2079 Ashwin (Back), Q2(b)

Data Structure and Algorithms · 5 marks

Open in the Padhaiko app

Topic: Definition of stack and its operations · Array implementation of…

Question

Convert the following infix expression to postfix expression with required status of stack.

Solution

Infix to Postfix Conversion Algorithm Rules:

  1. Operands are directly appended to the postfix output expression.
  2. Left parenthesis ( is pushed onto the operator stack.
  3. Operators (+, -, *, /) are pushed after popping any operators on the stack with greater or equal precedence (inside parentheses, ( has the lowest precedence). Precedence order: *, / > +, -.
  4. Right parenthesis ) pops operators from the stack and appends them to the postfix output until the matching ( is encountered, which is discarded.

Step-by-Step Stack Status and Postfix Trace: Tracing through each symbol of the given expression:

StepSymbol ScannedOperator Stack (Bottom Top)Postfix Output BufferAction Taken
1(((empty)Push (
2(( ((empty)Push (
3a( (aAppend operand a
4+( ( +aPush +
5(( ( + (aPush (
6(( ( + ( (aPush (
7b( ( + ( (a bAppend operand b
8*( ( + ( ( *a bPush *
9c( ( + ( ( *a b cAppend operand c
10)( ( + (a b c *Pop *, discard (
11/( ( + ( /a b c *Push /
12(( ( + ( / (a b c *Push (
13d( ( + ( / (a b c * dAppend operand d
14-( ( + ( / ( -a b c * dPush -
15e( ( + ( / ( -a b c * d eAppend operand e
16)( ( + ( /a b c * d e -Pop -, discard (
17)( ( +a b c * d e - /Pop /, discard (
18)(a b c * d e - / +Pop +, discard (
19)(empty)a b c * d e - / +Discard matching (

Algebraic Sub-expression Verification: Decomposing the parenthesized sub-expressions to verify correctness:

  1. Inner multiplication:
  2. Inner subtraction:
  3. Inner division:
  4. Outer addition:

Both the algorithmic stack simulation and structural derivation yield identical results.

Answer:

The converted postfix expression is:

(or in compact form: abc*de-/+)

All past exam questions for Data Structure and Algorithms