ACM刷题之路（十一）堆、栈、队列实现表达式转换

àì夳堔傛蜴生んèń 2024-02-19 12:19 32阅读 0赞

**这是《数据结构》这门课的课后练习题，很典型的一道题，总结记录一下**

--------------------

题目：表达式转换

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

#### 输入格式: ####

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

#### 输出格式: ####

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

#### 输入样例: ####

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

#### 输出样例: ####

2 3 7 4 - * + 8 4 / +

--------------------

**比如a+b\*c+(d\*e+f)\*g**

**string类型读入**

**如果遇到字母直接入队列**

**乘法除法优先级比加减法要高**

**优先级高的入站**

**优先级相等或者低的，先把高的入队列，再把当前的入栈**

**如果遇到‘（’直接入栈**

**如果遇到‘）’ 在堆栈中往头找，直到找到‘（’为止，并且删除堆栈中的‘（’**

#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;
    }