数据结构作业题：表达式转换（中缀转后缀） —— 栈

算术表达式有前缀表示法、中缀表示法和后缀表示法等形式。日常使用的算术表达式是采用中缀表示法，即二元运算符位于两个运算数中间。请设计程序将中缀表达式转换为后缀表达式。

输入格式:

输入在一行中给出不含空格的中缀表达式，可包含+、-、*、/以及左右括号()，表达式不超过20个字符。

输出格式:

在一行中输出转换后的后缀表达式，要求不同对象（运算数、运算符号）之间以空格分隔，但结尾不得有多余空格。

输入样例:

2+3*(7-4)+8/4

输出样例:

2 3 7 4 - * + 8 4 / +

#include<iostream>
#include<string>
#include<stack>
#include<queue>
using namespace std;
int main(void) {
    string a;
    getline(cin, a);
    stack<char> symbolx;
    queue<string> outstr;
    int flag = 0;//flag=0,表示表达式的开头,flag=1,不是开头
    for (int i = 0;i < a.length();i++) {
        if (flag == 0) {
            if (a[i] == '-') {
                flag = -1; //表达式开头的负号
                continue;
            } else if (a[i] == '+') {
                flag = 1;
                continue;
            }
        }
        if (a[i] >= '0' && a[i] <= '9') { //如果是数字
            string temp;//存放一个完整的数字
            if (flag == -1) {
                temp.push_back('-');
            }
            flag = 1; //有了一个数字，就肯定不是开头
            while (((a[i] >= '0' && a[i] <= '9') || a[i] == '.') && i < a.length()) {
                temp.push_back(a[i]);
                i++;
            }
            i--;//多加了一下，要复原回去
            outstr.push(temp);
        } else { //运算符和括号
            if (a[i] == '(') {
                flag = 0;//接下里就是表达式的开头了
                symbolx.push(a[i]);
                continue;
            }
            if (a[i] == ')') {
                char topstr;
                while (!symbolx.empty() && symbolx.top() != '(') {
                    topstr = symbolx.top();
                    string s;
                    s.push_back(topstr);
                    outstr.push(s);
                    symbolx.pop();
                }
                //把左括号弹出来
                if (!symbolx.empty() && symbolx.top() == '(') {
                    symbolx.pop();
                }
                continue;
            }
            switch (a[i]) {
            case '+':
            case '-':
                if (symbolx.empty()) {
                    symbolx.push(a[i]);
                } else {
                    char topstr;
                    //因为加减的优先级最低，所以一直出栈直到栈空或者左括号(
                    while (!symbolx.empty() && symbolx.top() != '(') {
                        topstr = symbolx.top();
                        string s;
                        s.push_back(topstr);
                        outstr.push(s);
                        symbolx.pop();
                    }
                    symbolx.push(a[i]); //当前符号入栈 
                }
                break;
            case '*':
            case '/':
                if (symbolx.empty()) {
                    symbolx.push(a[i]);
                } else {
                    char topstr;
                    //因为乘除的优先级大于加减，小于左边的乘除
                    if (!symbolx.empty() && symbolx.top() != '(') {
                        topstr = symbolx.top();
                        if (topstr == '*' || topstr == '/') { //前面有乘除法
                            string s;
                            s.push_back(topstr);
                            outstr.push(s);
                            symbolx.pop();
                        }
                    }
                    symbolx.push(a[i]); //当前符号入栈
                }
                break;
            }

        }
    }
    while (!symbolx.empty()) {
        string s;
        s.push_back(symbolx.top());
        if (symbolx.top() != '(') {
            outstr.push(s);
        }
        symbolx.pop();
    }
    int j = 0;
    while (!outstr.empty()) {
        if (j == 0) {
            cout << outstr.front();
            j++;
        } else {
            cout << " " << outstr.front();
        }
        outstr.pop();
    }
    return 0;
}