第10个样例RE了
#include<bits/stdc++.h>
using namespace std;
//a是数字栈,b是符号栈,c是答案队列
stack<int> op, ed;
stack<char> b;
queue<char> c, q;
int qmi(int a, int b) {
int res = 1;
while(b) {
if(b & 1) res = res * a;
a *= a;
b >>= 1;
}
return res;
}
int main()
{
string s;
cin >> s;
int len = s.size();
for(int i = 0;i < len;i++) {
//6级运算级
if(s[i] >= '0' && s[i] <= '9') {
c.push(s[i]);
}
//5级运算级
else if(s[i] == '+' || s[i] == '-') {
while(b.size()) {
auto t = b.top();
if(t == '(') break;
b.pop();
c.push(t);
}
b.push(s[i]);
}
//4级运算级
else if(s[i] == '*' || s[i] == '/') {
while(b.size()) {
auto t = b.top();
if(t == '+' || t == '-' || t == '(') break;
b.pop();
c.push(t);
}
b.push(s[i]);
}
//3级运算级
else if(s[i] == '^') {
c.push(s[i + 1]);
while(b.size()) {
auto t = b.top();
if(t != '^') break;
b.pop();
c.push(t);
}
b.push(s[i]);
i++;
}
//2级运算级
else if(s[i] == '(') b.push(s[i]);
//1级运算级
else {
while(b.size()) {
auto t = b.top();
b.pop();
if(t == '(') break;
c.push(t);
}
}
}
while(b.size()) {
auto t = b.top();
b.pop();
c.push(t);
}
while(c.size()) {
auto t = c.front();
c.pop();
q.push(t);
cout << t << ' ';
}
cout << '\n';
while(q.size()) {
c.push(q.front());
q.pop();
}
while(c.size()) {
auto t = c.front();
c.pop();
if(t >= '0' && t <= '9') op.push(t - '0');
else {
int x = op.top();
op.pop();
int y = op.top();
op.pop();
if(t == '+') op.push(y + x);
if(t == '-') op.push(y - x);
if(t == '*') op.push(y * x);
if(t == '/') op.push(y / x);
if(t == '^') op.push(qmi(y, x));
//输出左边数字
while(op.size()) {
ed.push(op.top());
op.pop();
}
while(ed.size()) {
auto t = ed.top();
ed.pop();
op.push(t);
cout << t << ' ';
}
//输出右边
while(c.size()) {
auto t = c.front();
c.pop();
q.push(t);
cout << t << ' ';
}
cout << '\n';
while(q.size()) {
c.push(q.front());
q.pop();
}
}
}
return 0;
}