更新时间:2023-02-18 11:55:16
从后缀转中缀比从中缀转后缀要简单,因为不需要处理运算符优先级的问题。
算法思路:
从左到右扫描后缀表达式中的符号,有两种情况:
如果是数字,则直接压栈。
如果是运算符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;
}