?
Solved

Postfix to Infix

Posted on 2000-02-01
8
Medium Priority
?
4,692 Views
Last Modified: 2009-01-12
I am able to understand the infix to postfix, however I am having trouble with putting the parentheses back into the infix if I start with postfix.

Have looked at possibility of using 2 stacks, however I would like to
use only one.

I may not have made it clear.

What I need is to convert it to a fully parenthesized infix expression.


I don't understand how I get the parentheses in right spot

slammer 14


Please help!!

slammer14
0
Comment
Question by:slammer14
8 Comments
 
LVL 4

Expert Comment

by:inpras
ID: 2480698
put some code here what U have tried so that we can help U
0
 
LVL 85

Expert Comment

by:ozo
ID: 2480985
What are the elements on your stack?  infix strings?
0
 

Accepted Solution

by:
bhattu earned 150 total points
ID: 2482464
You do not need to store the brackets in either the postfix or the prefix notation. The order in which you form the postfix/prefix notation will be different depending on the brackets, thus each time you have such a notation, you know exactly what is the order of execution. Hence, IMO you can restore, rather, reintroduce the brackets when you parse the tree formed by the postfix notation.

for eg. consider the following infix forms:-
(A+B)*C
A+(B*C)

now for the first one the postfix notation will be
AB+C*
and for the second one the notation will be
ABC*+

When you are parsing the tree formed by the above notations, you can remember what was the previous root, and whether its precedence is higher or not. If its precedence is higher, then introduce the brackets.
A+(B*C) gets converted to ABC*+ in the postfix notation, and when converting it back to infix, it gets converted to A+B*C, no brackets assuming * has higher precedence over +.
Similarly, AB+C* gets converted to (A+B)*C.

I hope I am clear.
Regards,
- Amit.
0
Never miss a deadline with monday.com

The revolutionary project management tool is here!   Plan visually with a single glance and make sure your projects get done.

 

Expert Comment

by:SISU
ID: 2499702
Hi,
  Here I am giving how we can evaluate postfix expression

Suppose the postfix expression is
  ab+c*
The corressponding infix expression is
  (a+b)*c

element   stack

  a         a       <-  Top
  b         a,b     <-  Top
  +         perform b+a & result is
            put onto top of the stack(a)
  c         a,c     <-  Top
  *         a*c

I think this will help U.

Sisu
0
 

Author Comment

by:slammer14
ID: 2501880
Edited text of question.
0
 

Author Comment

by:slammer14
ID: 2501916
Sisu thanks it helps a little, however I don't need to calculate answer I just have to give the expression.

My email is slammer14@hotmail.com

Thanks
slammer
0
 

Author Comment

by:slammer14
ID: 2501924
Adjusted points to 50
0
 
LVL 85

Expert Comment

by:ozo
ID: 2501996
While evaluation is easy from postfix, you may find infix conversion more convenient from prefix.
0

Featured Post

Never miss a deadline with monday.com

The revolutionary project management tool is here!   Plan visually with a single glance and make sure your projects get done.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

This article shows you how to optimize memory allocations in C++ using placement new. Applicable especially to usecases dealing with creation of large number of objects. A brief on problem: Lets take example problem for simplicity: - I have a G…
Article by: evilrix
Looking for a way to avoid searching through large data sets for data that doesn't exist? A Bloom Filter might be what you need. This data structure is a probabilistic filter that allows you to avoid unnecessary searches when you know the data defin…
The goal of the video will be to teach the user the difference and consequence of passing data by value vs passing data by reference in C++. An example of passing data by value as well as an example of passing data by reference will be be given. Bot…
The viewer will learn how to clear a vector as well as how to detect empty vectors in C++.

601 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question