杭电OJ 1123（C++）

#include <iostream>
#include <stack>
#include <string>
#include <cstring>
using namespace std;

struct Expre //后缀转中缀的临时表达式
{
	string exp = ""; //表达式
	int p = 0; //表达式优先级，操作数优先级为3，*,/优先级为2，+,-优先级为1
};

int priority(char c) //判断运算符优先级
{
	if (c == '+' || c == '-') return 1;
	else if (c == '*' || c == '/') return 2;
	else if (c == '(') return 3;
}

string middle2Back(string s) //中缀转后缀
{
	string t = ""; //后缀表达式
	stack<char> op; //运算符栈
	int n = s.length();
	char tmp;

	for (int i = 0; i < n; i++)
	{
		if (s[i] >= 'a' && s[i] <= 'z') //字符为小写字母，直接加入后缀表达式
			t += s[i];
		else if (s[i] == '(') //字符为左括号，直接入栈
			op.push(s[i]);
		else if (s[i] == ')')
		{ //字符为右括号，将栈中左括号上面的所有运算符依次出栈加入后缀表达式，
		  //并删除左括号
			while (!op.empty())
			{
				tmp = op.top();
				if (tmp == '(')
				{
					op.pop();
					break;
				}
				t += tmp;
				op.pop();
			}
		}
		else
		{ //字符为其他运算符，和栈顶运算符依次比较优先级，将优先级大于它的依次
		  //出栈加入后缀表达式，然后将该字符入栈
			while (!op.empty())
			{
				tmp = op.top();
				int p1 = priority(tmp); //栈顶字符的优先级
				int p2 = priority(s[i]); //该字符的优先级
				if (p2 > p1 || tmp == '(')
					break;
				t += tmp;
				op.pop();
			}
			op.push(s[i]);
		}
	}
	while (!op.empty())
	{ //中缀表达式所有字符处理完后，将栈中剩余字符依次出栈，加入后缀表达式
		t += op.top();
		op.pop();
	}
	return t;
}

string back2Middle(string t) //后缀转中缀
{
	stack<Expre> st;
	string a = "";
	string b = "";
	string x;
	Expre tmp;
	Expre ta, tb;
	int n = t.length();
	int p1;

	for (int i = 0; i < n; i++)
	{
		if (t[i] >= 'a' && t[i] <= 'z')
		{ //字符为小写字母，将其赋值给临时表达式，优先级设置为3，直接入栈
			tmp.exp = t[i];
			tmp.p = 3;
			st.push(tmp);
		}
		else if (t[i] == '+')
		{ //字符为'+'，将栈顶两个临时表达式出栈，用'+'连接为新的临时表达式，
		  //优先级设置为'+'的优先级，入栈
			b = st.top().exp; //栈顶临时表达式
			st.pop();
			a = st.top().exp; //次栈顶临时表达式
			st.pop();

			tmp.exp = a + '+' + b; //新的临时表达式
			tmp.p = 1; //新的临时表达式的优先级
			st.push(tmp);
		}
		else if (t[i] == '-')
		{ //字符为'-'，将栈顶两个临时表达式出栈，用'-'连接为新的临时表达式，
		  //优先级设置为'-'的优先级，入栈
			tb = st.top();
			st.pop();
			ta = st.top();
			st.pop();
			p1 = priority('-'); //'-'的优先级

			if (tb.p <= p1) //栈顶临时表达式的优先级小于'-'的优先级，则给其加括号
				b = '(' + tb.exp + ')';
			else 
				b = tb.exp;

			a = ta.exp;
			tmp.exp = a + '-' + b;
			tmp.p = 1;
			st.push(tmp);
		}
		else if (t[i] == '*')
		{ //字符为'*'，将栈顶两个临时表达式出栈，用'*'连接为新的临时表达式，
		  //优先级设置为'*'的优先级，入栈
			tb = st.top();
			st.pop();
			ta = st.top();
			st.pop();
			p1 = priority('*'); //'*'的优先级

			if (tb.p < p1) //栈顶临时表达式的优先级小于'*'的优先级，则给其加括号
				b = '(' + tb.exp + ')';
			else b = tb.exp;

			if (ta.p < p1) //次栈顶临时表达式的优先级小于'*'的优先级，则给其加括号
				a = '(' + ta.exp + ')';
			else a = ta.exp;

			tmp.exp = a + '*' + b;
			tmp.p = 2;
			st.push(tmp);
		}
		else if (t[i] == '/')
		{ //字符为'/'，将栈顶两个临时表达式出栈，用'/'连接为新的临时表达式，
		  //优先级设置为'/'的优先级，入栈
			tb = st.top();
			st.pop();
			ta = st.top();
			st.pop();
			p1 = priority('/'); //'/'的优先级

			if (tb.p <= p1)
				b = '(' + tb.exp + ')';
			else b = tb.exp;

			if (ta.p < p1)
				a = '(' + ta.exp + ')';
			else a = ta.exp;

			tmp.exp = a + '/' + b;
			tmp.p = 2;
			st.push(tmp);
		}
	}
	return st.top().exp;
}

int main()
{
	int n;
	cin >> n;
	string s; //原始中缀表达式
	string t; //后缀表达式
	string result; //后缀转回中缀（最少括号）
	while (n--)
	{
		cin >> s;
		t = middle2Back(s);
		result = back2Middle(t);
		cout << result << endl;
	}
	return 0;
}