这是《数据结构》这门课的课后练习题，很典型的一道题，总结记录一下
题目：表达式转换
算术表达式有前缀表示法、中缀表示法和后缀表示法等形式。日常使用的算术表达式是采用中缀表示法，即二元运算符位于两个运算数中间。请设计程序将中缀表达式转换为后缀表达式。
输入格式:
输入在一行中给出不含空格的中缀表达式，可包含 、-、*、以及左右括号()，表达式不超过20个字符。
输出格式:
在一行中输出转换后的后缀表达式，要求不同对象（运算数、运算符号）之间以空格分隔，但结尾不得有多余空格。
输入样例:
代码语言：javascript复制2 3*(7-4) 8/4输出样例:
代码语言：javascript复制2 3 7 4 - * 8 4 / 比如a b*c (d*e f)*g
string类型读入
如果遇到字母直接入队列
乘法除法优先级比加减法要高
优先级高的入站
优先级相等或者低的，先把高的入队列，再把当前的入栈
如果遇到‘（’直接入栈
如果遇到‘）’ 在堆栈中往头找，直到找到‘（’为止，并且删除堆栈中的‘（’
代码语言：javascript复制#include<iostream>
#include<string>
#include<queue>
#include<stack>
using namespace std;
int main(){
stack<string> s1;
queue<string> q1;
while (!s1.empty())
s1.pop();//初始化堆栈
while (!q1.empty())
q1.pop();//初始化队列
string s;
getline(cin, s);//输入
int len = s.size(), num = 0, i, j;
for (i = 0; i < len; i ){
string ts = "";
char c = s[i], prc = s[i - 1];//c代表当前字符 prc代表前面一个字符
if ((c == ' ' || c == '-') && (!i || prc == '(') || (c >= '0' && c <= '9'))
{//如果当前字符是数字或者第一个字符或者前面是左括号 直接入队列
if (c != ' ') ts = c;
while (s[i 1] == '.' || s[i 1] >= '0' && s[i 1] <= '9')//数字不一定是个位数
ts = s[ i];//数字整体写入到ts的string中
q1.push(ts);//进入队列
}
else if (c == ' ' || c == '-')
{
int flag = 1;//flag符号控制输入 避免如(-4)这样的情况出错
while (flag)
{
if (s1.empty() || s1.top() == "(")//如遇到(-4)这样的情况退出
s1.push(ts c), flag = 0;//如果顶部的优先级比当前的小，进入
else
{
q1.push(s1.top());//在压入加减之前，如果顶部是乘除，需要先拿掉
s1.pop();
}
}
}
else if (c == '*' || c == '/')
{
int flag = 1;
while (flag)
{
if (s1.empty() || s1.top() == "(" || s1.top() == " " || s1.top() == "-")
s1.push(ts c), flag = 0;//如果顶部优先级比当前的小，就压入
else
{
q1.push(s1.top());//否则先把优先级高的压入队列
s1.pop();
}
}
}
else if (c == '(')//左括号直接进入堆栈
s1.push(ts c);
else if (c == ')')//右括号直接循环到遇到左括号为止
{
int flag = 1;
while (flag)
{
string tp = s1.top();
if (tp == "(") s1.pop(), flag = 0;//遇到左括号直接退出
else
{
q1.push(s1.top());//没找到继续进入队列
s1.pop();
}
}
}
}
while (!s1.empty())
{
q1.push(s1.top());//剩余的全部依次压入堆栈
s1.pop();
}
if (!q1.empty())
{ //c_str()作用是将string转化为C语言的字符串
printf("%s", q1.front().c_str()); q1.pop();
}//否则string类型无法用%s这样输出
while (!q1.empty())
{
printf(" %s", q1.front().c_str()); q1.pop();
}
puts("");
return 0;
}
