UC知道C/C++，答对后可追加分数
来源：百度知道 编辑：UC知道 时间：2024/06/20 07:33:21
INPUT：
输入包含多组测试数据。第一行包括一个正整数T（1<=T<=100），表示测试数据的组数。接下来有T行数据，每行包括一个逆波兰表达式（这些表达式均以a-z或者+，-，*，/来表示，其中一个字母表示一个操作数，不会采用多个字母表述一个操作数的，其中操作数/运算符与操作数/运算符之间用一个空格隔开）。所有的逆波兰表达式都是合法的。
OUTPUT：
对于每组测试数据，请在一行里输出对应的波兰表达式。
Sample Input：
2
a b + c d + *
a b * c d e + * +
Sample Output：
（a+b）*（c+d）
a*b+c*(d+e)
提示：波兰表达式就是我们平时使用的常规算数表达式，如：（a+b）*(c+d)。逆波兰表达式就是对波兰表达式进行简化，把运算符都放在操作数之后。如：波兰表达式（a+b）*（c+d）转换成波兰表达式是：ab+cd+*
2楼这位大哥说的我不是很明白啊，我就只是对二叉树有点了解，能给出这道题的具体实现代码么？小弟不胜感激
输入包含多组测试数据。第一行包括一个正整数T（1<=T<=100），表示测试数据的组数。接下来有T行数据，每行包括一个逆波兰表达式（这些表达式均以a-z或者+，-，*，/来表示，其中一个字母表示一个操作数，不会采用多个字母表述一个操作数的，其中操作数/运算符与操作数/运算符之间用一个空格隔开）。所有的逆波兰表达式都是合法的。
OUTPUT：
对于每组测试数据，请在一行里输出对应的波兰表达式。
Sample Input：
2
a b + c d + *
a b * c d e + * +
Sample Output：
（a+b）*（c+d）
a*b+c*(d+e)
提示：波兰表达式就是我们平时使用的常规算数表达式，如：（a+b）*(c+d)。逆波兰表达式就是对波兰表达式进行简化，把运算符都放在操作数之后。如：波兰表达式（a+b）*（c+d）转换成波兰表达式是：ab+cd+*
2楼这位大哥说的我不是很明白啊，我就只是对二叉树有点了解，能给出这道题的具体实现代码么？小弟不胜感激
挨个语法元素读进来， 读到string里面。
如果这个语法元素是操作数，就压栈。 如果这个语法元素是操作符op，就出栈两个元素A,B ，按 (B) op (A)的形式写进一个string里， 然后把这个string压栈。 读完为止，栈里应该只剩下一个string，就是结果
按这样做的话 括号的处理可能需要另外有个记录， 就是说记录每个string里面的最后一级运算是个什么运算。 根据这个记录和当前的运算符号来决定要不要加括号。
比如你说的例子：
a b + c d + *
先是"a"入栈，然后"b"入栈，然后读到+ ，所以"b","a"出栈， "(a)+(b)"入栈， 然后"c" 入栈 "d"入栈，然后 读到+所以 "d","c"出栈， "(c)+(d)"入栈， 然后读到 * 所以 "(c)+(d)"和"(a)+(b)"出栈， "((a)+(b))*((c)+(d))"入栈， 读完了这时候栈里的 "((a)+(b))*((c)+(d))"就是结果
构造一棵树，如果你学过树应该知道。
非叶子为符号，叶子为数字如：
-----------------*
------------+--------+
---------a----b----c----d
表示(a+b) * (c+d)
所以，构造出这棵树，就很容易算了。（从叶子开始算）
采用一个中序遍历就出来了。将两个数的操作结果存在一个中间变量，这样会有两个中间变量，再将两个中间变量加起来就OK了。
因为要输入两个东东，那就构造两棵树就行了（三个就三棵呗）
关键是如何根据一个输入序列去构造出一棵树。
我们可以遍历这个序列，直到遇到一个操作符号，这样可以把这个符号的前两个数进行操作如：abc*-,
我们读入a,b,c时，都不会有操作