如何将后缀表达式转换为中缀表达式？c或者c++实现。

Question

中缀转换成后缀的我会，倒过来就通不过了。

Answer 1

“从后缀转中缀”比“从中缀转后缀”要简单，因为不需要处理运算符优先级的问题。

算法思路：

从左到右扫描后缀表达式中的符号，有两种情况：

1. 如果是数字，则直接压栈。

2. 如果是运算符op，则从栈顶弹出两个元素a和b，然后将(a op b)压栈。

最后栈顶的结果就是一个等价的中缀表达式，当然可能会有多余的括号，但不影响正确性。

下面是一个C++的实现，假设输入的后缀表达式是有效的，没有考虑错误处理。

#include <stack>
#include <vector>
#include <string>
#include <iostream>
using namespace std;
string postfix_to_infix(vector<string> expr) {
    stack<string> s;
    for (int i = 0; i < expr.size(); ++i) {
        // a number
        if (!expr[i].empty() && expr[i][0] >= '0' && expr[i][0] <= '9') {
            s.push(expr[i]);
        }
        // an operator
        else {
            string second = s.top(); s.pop();
            string first = s.top(); s.pop();
            s.push("(" + first + expr[i] + second + ")");
        }
    }
    return s.top();
}
int main() {
    vector<string> expr = {"3", "2", "5", "-", "6", "*", "3", "/", "+"};
    // output: (3+(((2-5)*6)/3))
    cout << postfix_to_infix(expr) << endl;
    return 0;
}