Postfix to Infix conversation [closed]

问题:

I can not solve this expression from postfix to infix. Please help me to understand in detail

5 x y - / x y + 3 ^ 7 / +

回答1:

postfix to infix:

5 x y - / x y + 3 ^ 7 / +

STEP

5 x y - /
A) 5xy-/ = 5 (x-y)/ = (5 / (x-y))
x y +
B) x y + = (x + y)
(x+y) 3 ^
B.1) (x + y) 3 ^ = ((x + y) ^ 3 )
Now, (5 / (x-y)) ((x + y) ^ 3 ) 7 / +
= (5 / (x-y)) (((x + y) ^ 3 )/7 ) + = (5 / (x-y)) + (((x + y) ^ 3 )/7 )

POSTFIX and PREFIX are expression in which no brackets are used. Precedence of operator are decided in order of there appearance in expression, So to evaluate expression no need to search next operation to perform- FAST .

While in INFIX expression precedence of operators are overwritten by brackets. hence brackets are there in infix expression- Need to search which operation to perform e.g. A+B%D - hence SLOW.
That is the reason conversion are useful in computer science.

回答2:

This is not the code but the way, you should expand a postfix to infix::

5 x y - / x y + 3 ^ 7 / +

5 (x-y) / xy+ 3^ 7 / +

(5/(x-y)) xy+ 3^ 7 / +

(5/(x-y)) (x+y)3^ 7 / +

(5/(x-y)) ((x+y)^3) 7 / +

(5/(x-y)) (((x+y)^3) / 7) +

(5/(x-y)) + (((x+y)^3) / 7)

回答3:

It is fairly straight forward:

1. You read an argument and decide if it is a value or a variable. If it is, you push the argument on the stack. If it isn't it is an operator.
2. If you have an operator, you create a tree consisting of the operator as the root and as many arguments of the stack as its children. You push the tree on the stack.
3. When you want to print the infix notation you do an in-order walk of the top of the stack (the original post-fix notation is just a post-order walk of the same tree).

To deal with this in C++ I create a base class (Expression) with derived class representing the different kinds of nodes (Value, Variable, and BinaryOperation) and maintain a std::stack<std::shared_ptr<Expression>>. Coding this out is mainly a typing exercise.