时间限制: 1.0 Sec 内存限制: 128 MB
题目描述
给定一个中缀表达式,请你输出其对应的后缀表达式
输入
输入一行字符串 s (|s| ≤ 100)表示一个合法的中缀表达式,且其中的数字都在INT范围内,同时也保证只会出现 +,-,*,/, (,) 这几种符号。
输出
输出一行,表示该中缀表达式所对应的后缀表达式,中间用空格隔开。
样例输入1 复制
9+(3-11)*3+8/2
样例输出1 复制
9 3 11 - 3 * + 8 2 / +
题目链接:hat8.zemeitong.cn/askai/1002?channel=bdtoufangztAskHD5
代码:
#include<bits/stdc++.h>
using namespace std;
string s;
stack<char> st;
int main()
{
cin>>s;
map<char, int>mp = {{'+', 1}, {'-', 1}, {'*', 2}, {'/', 2}};
for(int i = 0; i < s.length(); i ++)
{
if(isdigit(s[i]))
{
int j = i;
int val = 0;
while(j < s.length() && isdigit(s[j]))
{
val = val * 10 + s[j] - '0';
j ++;
}
i = j - 1;
cout<<val<<" ";
}
else
{
if(s[i] == '(')
{
st.push('(');
}
else if(s[i] == ')')
{
while(st.top() != '(')
{
cout<<st.top()<<" ";
st.pop();
}
st.pop();
}
else
{
while(st.size() > 0 && st.top() != '(' && mp[st.top()] >= mp[s[i]])
{
cout<<st.top()<<" ";
st.pop();
}
st.push(s[i]);
}
}
}
while(st.size())
{
cout<<st.top()<<" ";
st.pop();
}
return 0;
}