0
30kviews
Convert following infix expression into prefix and postfix format

(ab-(c+d/e^f)-g)h

Write an algorithm Conversion () to convert infix expression into prefix expression

1
489views

Given expression is (ab-(c+d/e^f)-g)h

Following is the above infix expression enclosed in brackets:

((ab-(c+d/e^f)-g)h)

1. Conversion from infix to postfix:

Character Scanned Stack Expression
( ( Empty
( (( Empty
a (( a
* ((* a
b ((* ab
- ((- ab*
( ((-( ab*
c ((-( ab*c
+ ((-(+ ab*c
d ((-(+ ab*cd
/ ((-(+/ ab*cd
e ((-(+/ ab*cde
^ ((-(+/^ ab*cde
f ((-(+/^ ab*cdef
) ((- ab*cdef^/+
- ((- ab*cdef^/+-
g ((- ab*cdef^/+-g
) ( ab*cdef^/+-g-
* (* ab*cdef^/+-g-
h (* ab*cdef^/+-g-h
) Empty abcdef^/+-g-h

Thus, the postfix expression is: abcdef^/+-g-h

2. Conversion from infix to prefix :

Reverse the given expression string to obtain h(g-(f^e/d+c)-ba). Enclosing the reversed string in brackets to obtain (h(g-(f^e/d+c)-ba))

Calculating the postfix expression of the reversed expression:

Character Scanned Stack Expression
( ( Empty
h ( h
* (* h
( (*( h
g (*( hg
- (*(- hg
( (*(-( hg
f (*(-( hgf
^ (*(-(^ hgf
e (*(-(^ hgfe
/ (*(-(/ hgfe^
d (*(-(/ hgfe^d
+ (*(-(+ hgfe^d/
c (*(-(+ hgfe^d/c
) (*(- hgfe^d/c+
- (*(- hgfe^d/c+-
b (*(- hgfe^d/c+-b
* ((- hgfe^d/c+-b
a ((- hgfe^d/c+-ba
) (* hgfe^d/c+-ba*-
) Empty hgfe^d/c+-ba-

Thus, the postfix expression obtained is: hgfe^d/c+-ba-

Reversing the postfix expression obtained gives the prefix expression.

Prefix expression: -ab-+c/d^efgh

Algorithm to convert from infix to prefix:

1. START
2. INPUT the expression EXPR from the user.
3. Reverse the EXPR obtained in step 1 to obtain REVEXPR. While reversing the string interchange the right and left parentheses. REVEXPR → REVERSE(EXPR)
4. Calculate the POSTFIX expression of the reversed string. POSTFIXEXPR → POSTFIX(REVEXPR)
5. Reverse the POSTFIXEXPR to obtain the Prefix expression PREFIXEXPR. PREFIXEXPR→ REVERSE(POSTFIXEXPR)
6. STOP