中缀转后缀
作者:
我是高情商
,
2024-10-04 17:54:03
,
所有人可见
,
阅读 3
#include <iostream>
#include <stack>
#include <string>
#include <unordered_map>
using namespace std;
stack<char>op;//存运算符
//用哈希表定义优先级,乘除优先级高于加减
unordered_map<char,int>h{{'+',1},{'-',1},{'*',2},{'/',2}};
void eval()
{
auto c=op.top();
op.pop();
cout<<c<<" ";
//中缀转后缀
//auto c=op.top();
//op.pop()
//cout<<c<" "
}
int main()
{
string s;//读入表达式
cin >> s;
for (int i = 0;i<s.size();i++)
{
if(isdigit(s[i]))
{
//如果是数字则直接入栈
int x=0,j=i;
//在字符串中计算数字
while(j<s.size()&&isdigit(s[j]))
{
x=x*10+s[j]-'0';
j++;
}
cout<<x<<" ";
//中缀转后缀,遇到数字直接输出cout<<x<<" ",数栈没用;
i=j-1;//while循环结束后j多加了一个,要将i返回到最后一个数字
}
else if(s[i]=='(')
{
op.push(s[i]);//左括号直接入栈
}
else if(s[i]==')')
{
//弹到左括号为止
while(op.top()!='(')
{
eval();
}
op.pop();//弹出左括号
}
else
{
//栈顶元素优先级大于等于当前元素优先级
while(op.size()&&h[op.top()] >= h[s[i]])
{
eval();
}
op.push(s[i]);
}
}
while(op.size())eval();
//结果为数栈的栈顶元素
return 0;
}