疑问：求表达式a+b*(c-d)-e/f的波兰式和逆波兰式。

Question

为什么在网上找都是相同的答案。按理说，给定一个表达式应该是知道相对的中序表达式而已，它不能唯一确定一个二叉树啊？？我画了差不多3个二叉树，中序表达式都是这个，但是前序后序表达式每个都不一样。

刚学数据结构，蛮多不懂的，有好心人能告诉我么，是我题目理解错了？？还是这个题本身就不是唯一解啊？？

Answer 1

a*b*c → **abc
a*b*c+c*d → +**abc*cd
(a+b)*((c-d)*e+f) → *+ab+*-cdef

上面是波兰式，逆波兰式如下:

a*b*c → ab*c*
a*b*c+c*d → ab*c*cd*+
(a+b)*((c-d)*e+f) → ab+cd-e*f+*

写出(a+b)*((c-d)*e+f)转换时栈的变化情况:【注意，右端为栈顶】

读入(，入栈，栈中为(，输出:(空);
读入a，直接输出，栈中为(，输出:a;
读入+，入栈，栈中为(+，输出:a;
读入b，直接输出，栈中为(+，输出:ab;
读入)，依次推出栈中的符号，直到遇见一个(【注意括号不输出】，栈中为空，输出:ab+;
读入*，入栈，栈中为*，输出:ab+;
读入(，入栈，栈中为*(，输出:ab+;
读入(，入栈，栈中为*((，输出:ab+;
读入c，直接输出，栈中为*((，输出:ab+c;
读入-，入栈，栈中为*((-，输出:ab+c;
读入d，直接输出，栈中为*((-，输出:ab+cd;
读入)，依次推出栈中的符号，直到遇见一个(【注意括号不输出】，栈中为*(，输出:ab+cd-;
读入*，入栈，栈中为*(*，输出:ab+cd-;
读入e，直接输出，栈中为*(*，输出:ab+cd-e;
读入+，【由于此时栈中的*的优先级高于+，所以先将*退栈，然后+入栈】，栈中为*(+，输出:ab+cd-e*;
读入f，直接输出，栈中为*(+，输出:ab+cd-e*f;
读入)，依次推出栈中的符号，直到遇见一个(【注意括号不输出】，栈中为*，输出:ab+cd-e*f+;
此时读入已经完毕，栈中还剩一个*，输出:ab+cd-e*f+*
完毕!

以上就是整个从中缀表达式到后缀表达式的过程，栈的变化情况已经都写出来了。