后缀表达式

基于STL的中缀转后缀实现

1.定义分析

首先明确后缀表达式的定义

后缀表达式是一种不需要括号的表达式，这表示在将中缀表达式转化为后缀表达式时，如果中缀表达式中存在括号，不能将括号写入后缀表达式

那么这里引出一个问题，后缀表达式中不存在括号那要如何表示运算的优先级？

理解后缀表达式的运算过程

以(1+5-4)*(6-9)为例，它的后缀表达式是15+4-69-*

先分析中缀表达式的运算过程，参与运算过程的操作符依次是+ - - *，正好是后缀表达式中从左往右的操作符顺序。而操作符所涉及到的2个操作数都是位于该操作符的前面。

那么回到上面的问题来看，中缀表达式中的括号的作用如何在后缀表达式中体现出来？

以1+2*3、(1+2)*3为例

1+2*3的后缀表达式为123*+

(1+2)*3的后缀表达式为12+3*

通过对比可以发现当表达式中存在括号时，括号中的操作符提前输出了，这表示在遇到括号的情况时，可以将括号内的操作符提前输出。

此外，还需要考虑四则运算中，乘除的优先级高于加减

以1+2*3为例，如果不加以判断直接转化后缀表达式，结果为12+3*，先运算+再运算*，这显然违背了基本的四则运算法则，实际上正确的结果应该是123*+

通过对比两个结果，可以发现优先级较低的操作符移到了后面，这表示在运算过程中可以先将优先级低的操作符存储起来，而将优先级高的运算符输出。

2.思路分析

采用STL模板实现中缀转后缀，这里使用的是stack。定义一个stack字符栈专门用于存储操作符

这里特别说明一下字符栈，字符栈栈底的操作符优先级最低，栈顶的操作符优先级最高

1.输入中缀表达式的字符串依次获取字符串中的每个字符

2.对字符进行以下的判断和操作

数字字符，直接输出
左括号字符，直接存入stack
右括号字符，将stack中的操作符依次输出，直到遇到左括号时停止，将左括号出栈但不输出
加减乘除字符
- 优先级高的字符直接存入stack
- 优先级低的字符，则比较当前字符栈栈顶操作符的优先级，遇到优先级更低的操作符或左括号字符时不出栈，并将当前操作符入栈

3.当字符串遍历完成后，再依次输出字符栈内剩余的操作符

3.实现过程分析

以(1+5-4)*(6-9)为例，字符串长度为13

获取到的字符：(

表达式：
字符栈：(

获取到的字符：1

表达式：1
字符栈：(

获取到的字符：+

表达式：1
字符栈：(+

获取到的字符：5

表达式：15
字符栈：(+

获取到的字符：-

表达式：15+
字符栈：(-

获取到的字符：4

表达式：15+4
字符栈：(-

获取到的字符：)

表达式：15+4-
字符栈：

获取到的字符：*

表达式：15+4-
字符栈：*

获取到的字符：(

表达式：15+4-
字符栈：*(

获取到的字符：6

表达式：15+4-6
字符栈：*(

获取到的字符：-

表达式：15+4-6
字符栈：*(-

获取到的字符：9

表达式：15+4-69
字符栈：*(-

获取到的字符：)

表达式：15+4-69-
字符栈：*

最后，依次输出字符栈中所有的操作符

表达式：15+4-69-*

4.源代码

#include <iostream>
#include <algorithm>
#include <stack>
#include <list>
using namespace std;

list<string> transfer(string s)
{
    int len = s.length(); //记录长度
    list<string> listIn;  //存储中缀表达式
    list<string> listOut; //存储后缀表达式
    stack<char> symbol;   //符号栈
    stack<char> ans;      //结果表达式

    listIn.push_back(s);
    for (int i = 0; i < len; i++)
    {
        //思路
        //数字直接存入ans
        //运算符:
        //如果是'('直接存入symbol
        //如果是')'依次出栈symbol中的运算符并存入ans, 直到遇到'(', '('不存入ans
        //其他符号, 依次出栈symbol中的运算符并存入ans, 直到遇到优先级更低的运算符或'('时, 将当前符号存入symbol
        //字符串遍历完成后, 依次出栈符号栈中剩余的运算符并存入ans
        if (listIn.back()[i] >= '0' && listIn.back()[i] <= '9')
            ans.push(listIn.back()[i]);
        else if (listIn.back()[i] == '(')
            symbol.push(listIn.back()[i]);
        else if (listIn.back()[i] == ')')
        {
            while (symbol.top() != '(')
            {
                ans.push(symbol.top());
                symbol.pop();
            }
            symbol.pop(); //将'('出栈
        }
        else
        {
            //这里手动优先考虑乘除的优先级高于加减
            if (listIn.back()[i] == '+' || listIn.back()[i] == '-') //加减符号优先级最低
            {
                while (!symbol.empty() && symbol.top() != '(')
                {
                    ans.push(symbol.top()); //直接存入symbol中的运算符
                    symbol.pop();
                }
                symbol.push(listIn.back()[i]); //符号栈存入当前从listIn中获取的符号
            }
            else //乘除符号优先级高直接存入符号栈
            {
                symbol.push(listIn.back()[i]);
            }
        }
    }

    while (!symbol.empty())
    {
        ans.push(symbol.top());
        symbol.pop();
    }

    //将结果表达式的值存入listOut
    //先利用已经清空的symbol实现反转
    while (!ans.empty())
    {
        symbol.push(ans.top());
        ans.pop();
    }

    string res = "";
    while (!symbol.empty())
    {
        res += symbol.top();
        symbol.pop();
    }
    listOut.push_back(res);

    return listOut;
}

int main()
{
    string s;
    while (cin >> s)
    {
        list<string> res = transfer(s);
        cout << res.front() << "\n";
    }
}

树下集熵