问题:
Description
由小写字母{'a','b','c','d','z'}和{'+','-','*','/','(',')'}可以组成一个中缀表达式,现在需要你输出它的后缀表达式。
Input
输入的第一行是一个int型整数T,表示一个有T组数据。
接下来T行,每行一个一个不含空格的字符串,且每个字符串长度都小于1000。该字符串就是中缀表达式。
数据保证输入的表达式一定合法。
Output
输出T行,每行一个后缀表达式,表示求得的结果。输出的表达式同样不含空格。
Sample Input
2
a+bc+(de+f)*g
(a+b)*c/d+f/g
Sample Output
abc*+def+g+
ab+c*d/fg/+
我的代码如下:
#include <iostream>
#include <string>
#include <stack>;
using namespace std;
//操作符的栈内、外优先级
int isp(char x)//栈内
{
if (x == '*' || x == '/') return 5;
if (x == '+' || x == '-') return 3;
if (x == '(') return 1;
else return -1;
}
int icp(char x)//栈外
{
if (x == '*' || x == '/') return 4;
if (x == '+' || x == '-') return 2;
if (x == '(') return 6;
else return -1;
}
int main()
{
string infix, postfix;
stack<char> operators;
int T;
cin >> T;
char ch;
for (int q = 0; q < T; ++q)
{
cin >> infix;
for (int i = 0; i < infix.size(); i++)
{
ch = infix[i];
if (ch >= 'a' && ch <= 'z')
{//是操作数,输出
postfix.push_back(ch);
}
else if (operators.empty())
{//若是空的,让该操作符进栈
operators.push(ch);
}
else if (ch == ')')
{
while (operators.top() != '(' && !operators.empty())
{
postfix.push_back(operators.top());
operators.pop();
}
operators.pop();
}
else if (ch == '(')
{
operators.push(ch);
}
else if (ch == '+' || ch == '-'
|| ch == '*' || ch == '/')
{//是加减乘除
while (isp(operators.top()) >= icp(ch))
{
postfix.push_back(operators.top());
operators.pop();
if (operators.empty())
{
break;
}
}
operators.push(ch);
}
}
while (!operators.empty())
{
postfix.push_back(operators.top());
operators.pop();
}
cout << postfix << endl;
infix.clear();
postfix.clear();
}
return 0;
}