written 8.4 years ago by | modified 2.0 years ago by |
(ab-(c+d/e^f)-g)h
Write an algorithm Conversion () to convert infix expression into prefix expression
written 8.4 years ago by | modified 2.0 years ago by |
(ab-(c+d/e^f)-g)h
Write an algorithm Conversion () to convert infix expression into prefix expression
written 8.4 years ago by |
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: