Skip to main content

Convert expression to prefix and postfix

Short answer

Postfix: abc^*d-ef/g*k1-/+. Prefix: +-*a^bcd/*/efg-k1. Stack top algorithm: if top==-1 report error, else return S[top].

Convert ab^c-d+(e/fg)/(k-1) into prefix and postfix expression. Write an algorithm for top of stack fix stack operation.

Infix: a * b ^ c - d + ( e / f * g ) / ( k - 1 ). Precedence: ^ (right-associative) > * / > + -. The last bracket is read as (k - 1) with the digit 1.

Postfix (scan left to right with a stack)

StepSymbolStack (bottom → top)Postfix output
1a(empty)a
2**a
3b*ab
4^*^ab
5c*^abc
6--abc^*
7d-abc^*d
8++abc^*d-
9(+(abc^*d-
10e+(abc^*d-e
11/+(/abc^*d-e
12f+(/abc^*d-ef
13*+(*abc^*d-ef/
14g+(*abc^*d-ef/g
15)+abc^*d-ef/g*
16/+/abc^*d-ef/g*
17(+/(abc^*d-ef/g*
18k+/(abc^*d-ef/g*k
19-+/(-abc^*d-ef/g*k
201+/(-abc^*d-ef/g*k1
21)+/abc^*d-ef/g*k1-
end(pop all)(empty)abc^*d-ef/g*k1-/+

Postfix: abc^*d-ef/g*k1-/+

Prefix (reverse the infix, swap brackets, convert like postfix, reverse the result)

Reversed infix with swapped brackets: ( 1 - k ) / ( g * f / e ) + d - c ^ b * a. For prefix, an incoming operator pops only operators of strictly higher precedence (^ pops equal), because the output is reversed at the end.

StepSymbol (of reversed string)StackOutput (before reversing)
1((-
21(1
3-(-1
4k(-1k
5)(empty)1k-
6//1k-
7(/(1k-
8g/(1k-g
9*/(*1k-g
10f/(*1k-gf
11//(*/1k-gf
12e/(*/1k-gfe
13)/1k-gfe/*
14++1k-gfe/*/
15d+1k-gfe/*/d
16-+-1k-gfe/*/d
17c+-1k-gfe/*/dc
18^+-^1k-gfe/*/dc
19b+-^1k-gfe/*/dcb
20*+-*1k-gfe/*/dcb^
21a+-*1k-gfe/*/dcb^a
end(pop all)(empty)1k-gfe/*/dcb^a*-+

Reverse the final output: Prefix: +-*a^bcd/*/efg-k1

Algorithms for stack operations (array S[0..MAX-1], top = -1 initially)

PUSH(S, x)
1. if top == MAX - 1:  print "Stack overflow"; return
2. top = top + 1
3. S[top] = x

POP(S)
1. if top == -1:  print "Stack underflow"; return ERROR
2. x = S[top]
3. top = top - 1
4. return x

STACKTOP(S)               /* peek: read top without removing */
1. if top == -1:  print "Stack empty"; return ERROR
2. return S[top]

(The final part of the question is read as asking for the stack-top/peek operation together with push and pop.)

✓ Answer checked by Claude Opus 5.5 (high effort)

Related questions

All Data Structure and Algorithm chapter 2 questions →