数据结构 - 如何将后缀表达式转换为中缀表达式?c或者c++实现。
本文介绍了数据结构 - 如何将后缀表达式转换为中缀表达式?c或者c++实现。的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!
问题描述
问 题
中缀转换成后缀的我会,倒过来就通不过了。
解决方案
从后缀转中缀比从中缀转后缀要简单,因为不需要处理运算符优先级的问题。
算法思路:
从左到右扫描后缀表达式中的符号,有两种情况:
如果是数字,则直接压栈。
如果是运算符
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;
}
这篇关于数据结构 - 如何将后缀表达式转换为中缀表达式?c或者c++实现。的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!
查看全文