0
已解决
新手光能
http://judge.codingtang.com/problem/1785/
和 前缀转后缀差不多，我两题都没写出来，求大佬思路（最好伪代码）
1785 后缀转前缀
题目描述 Description
对于表达式，我们在生活中常见的是它的中缀形式，但在计算机中会用到表达式的前缀表示和后缀表示。 例如：对于中缀表达式 3 + 4 的前缀表达式为 + 3 4，后缀表达式为3 4 +。
前缀和后缀的含义分别为： 前缀：先写运算符，接着是第一个操作数，最后是第二个操作数； 后缀：先写第一个操作数，接着写第二个操作数，最后写运算符。 例如：( 5 - 4 ) - 2 的前缀为 - - 5 4 2，后缀为 5 4 - 2
现在给你一个后缀表达式，请你输出它所对应的前缀表达式。
输入描述 Input Description
输入一个后缀表达式，运算符只有“+”和“-”，操作数都是只有1个位数字(0到9)，运算符和操作数之间都用一个空格隔开，表达式没有前导空格。每个表达式都是合法的，并且运算符不超过20个。
输出描述 Output Description
输出对应的前缀表达式。
样例输入 Sample Input
3 4 +
样例输出 Sample Output
+ 3 4
@葛新 @樊澄宇 @贾文卓 @酷町喵~o( =∩ω∩= )o~ 
0
已采纳
初级天翼
(1) 从右至左扫描，将6、5、4、3压入堆栈； (2) 遇到+运算符，因此弹出3和4（3为栈顶元素，4为次顶元素，注意与后缀表达式做比较），计算出3+4的值，得7，再将7入栈； (3) 接下来是×运算符，因此弹出7和5，计算出7×5=35，将35入栈； (4) 最后是-运算符，计算出35-6的值，即29，由此得出最终结果。 可以看出，用计算机计算前缀表达式的值是很容易的。 将中缀表达式转换为前缀表达式： 遵循以下步骤： (1) 初始化两个栈：运算符栈S1和储存中间结果的栈S2； (2) 从右至左扫描中缀表达式； (3) 遇到操作数时，将其压入S2； (4) 遇到运算符时，比较其与S1栈顶运算符的优先级： (4-1) 如果S1为空，或栈顶运算符为右括号“)”，则直接将此运算符入栈； (4-2) 否则，若优先级比栈顶运算符的较高或相等，也将运算符压入S1； (4-3) 否则，将S1栈顶的运算符弹出并压入到S2中，再次转到(4-1)与S1中新的栈顶运算符相比较； (5) 遇到括号时： (5-1) 如果是右括号“)”，则直接压入S1； (5-2) 如果是左括号“(”，则依次弹出S1栈顶的运算符，并压入S2，直到遇到右括号为止，此时将这一对括号丢弃； (6) 重复步骤(2)至(5)，直到表达式的最左边； (7) 将S1中剩余的运算符依次弹出并压入S2； (8) 依次弹出S2中的元素并输出，结果即为中缀表达式对应的前缀表达式。 例如，将中缀表达式“1+((2+3)×4)-5”转换为前缀表达式的过程
0
中级光能
可以用栈
0
高级光能
sorry我不知道
王子凡在2018-03-02 17:06:39追加了内容
在网上应该可以查到
0
初级天翼
正如他们所说
0
高级天翼
用栈
0
高级天翼
对，就像他们所说的。
0
缔造者
1
0
缔造者之神
1
