written 8.2 years ago by | modified 22 months ago by |

**(a b-(c+d/e^f)-g)h**

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

**1 Answer**

0

32kviews

Convert following infix expression into prefix and postfix format

written 8.2 years ago by | modified 22 months ago by |

**(a b-(c+d/e^f)-g)h**

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

ADD COMMENT
EDIT

1

535views

written 8.2 years ago by |

Given expression is (a*b-(c+d/e^f)-g)*h

Following is the above infix expression enclosed in brackets:

((a*b-(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: ab cdef^/+-g-h**

**2. Conversion from infix to prefix :**

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

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:

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

ADD COMMENT
EDIT

Please log in to add an answer.