题目：
表达式的转换 - 洛谷 P1175 - Virtual Judge
思路：
这道题可以拆成两问：
第一问，将中缀表达式转成后缀表达式放入一个数组
第二问，将后缀表达式的数组计算，并输出过程
第一问思路：
通过栈 递归的思路来解决，遍历中缀表达式，如果是数字则直接加入后缀表达式的数组。
如果是操作符要分如下三种情况：
1.栈为空，直接将操作符入栈。 2.栈不为空，该操作符比栈顶操作符优先级高，直接入栈。 3.栈不为空，该操作符比栈顶操作符优先级低或者相等，出栈顶操作符，加入后缀表达式的数组，并继续与下一个栈顶操作符判断。（两个^比较时，后来的^优先级更高，这是本题的特例）
重点：
遇到括号时：
遇到左括号，开始递归，创建新的栈，先将括号里的转成后缀表达式。
遇到右括号，递归结束，讲栈中元素全部加入后缀表达式的数组。（详细看代码中的注释）
第二问思路：
现在我们已经拿到了一个后缀表达式，并存在数组里。
后缀表达式的计算，遍历后缀表达式数组，遇到数字将其入栈，遇到操作符，出两次栈顶元素并将结果入栈。
由于我们要打印过程，但STL中的stack并不支持随机访问，我们可以用vector来模拟栈的使用，没计算一次打印 vector中的元素 后缀表达式数组中剩下的元素。
详细讲解在代码中，步骤都有注释。
AC代码：
代码语言：javascript复制#include<iostream>
#include<stdio.h>
#include<string>
#include<stack>
#include<vector>
#include<math.h>
using namespace std;
vector<char> ret;//ret数组用于存放后缀表达式
char str[1000001];//str数组存放输入的中缀表达式
char* p = str;//通过p指针来遍历
//compare函数用于比较操作符的优先级
int compare(char a, char b)
{
if (a == ' ' || a == '-')
{
if (b == '*' || b == '/' || b == '^') return -1;
else return 0;
}
else if (b == ' ' || b == '-')
{
if (a == '*' || a == '/' || a == '^') return 1;
else return 0;
}
else if (a == '*' || a == '/')
{
if (b == '^') return -1;
else return 0;
}
else if (b == '*' || b == '/')
{
if (a == '^') return 1;
else return 0;
}
//根据题意，两个^在一起时，应该判定后面来的^优先级更高
else if (a == '^' && b == '^')
{
return 1;
}
else return 0;
}
//suffix函数作用 从p1指向的位置开始进行转后缀操作
void suffix(char* p1)
{
//这里对全局变量p赋值是为了防止有递归结束，回溯后p指针回到进入递归的位置，我们要求p一直走不会因为递归结束后回来
p = p1;
//每次递归都要有新的栈，所以栈在函数体里创建
stack<char> st;
while(*p)
{
//如果遇到左括号，开始从这个括号右边的一个位置开始递归
if (*p == '(')
{
p ;
suffix(p);
//递归完如果已经走到str结尾就直接break，防止出现RE
if (*p == ' ')break;
}
//遇到右括号递归结束
else if (*p == ')')
{
//递归结束前全部操作符出栈，加入ret数组
while (!st.empty())
{
char t = st.top();
ret.push_back(t);
ret.push_back(' ');
st.pop();
}
//把p调整到右括号的右边一个位置，方便后续操作
p ;
return;
}
if (*p >= '0' && *p <= '9')//数字直接存入答案数组
{
ret.push_back(*p);
ret.push_back(' ');
}
else//操作符入栈
{
char t;
if (!st.empty()) t = st.top();
while(1)
{
//当前操作符优先级比栈顶大，入栈
if (st.empty()||compare(*p, t) > 0)
{
st.push(*p);
t = st.top();
break;
}
//比栈顶低或者等于，出栈顶操作符，加入答案数组
else if (compare(*p, t) <= 0)
{
ret.push_back(t);
ret.push_back(' ');
st.pop();
if (!st.empty()) t = st.top();
}
}
}
p ;
}
//遍历str结束。如果栈中还有元素，则全部出栈
while (!st.empty())
{
ret.push_back(st.top());
ret.push_back(' ');
st.pop();
}
}
//work函数用于最后计算过程的打印
void work()
{
//因为要遍历打印，所以后缀表达式计算式的栈没有用stack，而是用vector，
//因为stack无法遍历，而vector可以遍历且可以当栈使用
vector<int> st1;
int i = 0;
for (i = 0;i < ret.size();i )
{
//数字直接入栈
if (ret[i] >= '0' && ret[i] <= '9')
{
st1.push_back(ret[i] - '0');
}
//空格不管直接跳过
else if (ret[i] == ' ')
{
continue;
}
//剩下的都是操作符
//操作符出现，开始出两个栈中元素进行计算
else
{
int right = st1.back();//右操作数
st1.pop_back();
int left = st1.back();//左操作数
st1.pop_back();
//进行计算，并将结果入栈
if (ret[i] == ' ') st1.push_back(left right);
else if (ret[i] == '^') st1.push_back(pow(left,right));
else if (ret[i] == '-') st1.push_back(left - right);
else if (ret[i] == '*') st1.push_back(left * right);
else if (ret[i] == '/') st1.push_back(left / right);
//每进行一次计算，打印一次过程
//第一个for打印栈中元素
for (int j = 0;j < st1.size();j )cout << st1[j]<<' ';
//第二个for打印没在栈中的ret数组中的元素
for (int j = i 2;j < ret.size() - 1;j )cout << ret[j];
//如果是最后一步则不用打印换行
if (i == ret.size() - 2)continue;
cout << endl;
}
}
}
int main()
{
scanf("%s",str);
suffix(p);
//此时得到后缀表达式全在ret数组里
//根据题意先把ret打印一遍
for (int i = 0;i < ret.size() - 1;i )
{
cout << ret[i];
}
cout << endl;
//work函数打印后续计算过程
work();
return 0;
}
