栈的应用之表达式求值（后缀式运算）

亦凉 2021-09-22 12:46 263阅读 0赞

**1、逆波兰表达式简介**

假定给定一个只 包含 加、减、乘、除，和括号的算术表达式，你怎么编写程序计算出其结果。问题是：在表达式中，括号，以及括号的多层嵌套 的使用，运算符的优先级不同等因素，使得一个算术表达式在计算时，运算顺序往往因表达式的内容而定，不具规律性。 这样很难编写出统一的计算指令。  
  使用逆波兰算法可以轻松解决。他的核心思想是将普通的中缀表达式转换为后缀表达式。

转换为后缀表达式的好处是：

*  去除原来表达式中的括号，因为括号只指示运算顺序，不是完成计算必须的元素。
 *  使得运算顺序有规律可寻，计算机能编写出代码完成计算。虽然后缀表达式不利于人阅读，但利于计算机处理。

**2、将中缀表达式转换成后缀式（逆波兰表达式）**

1. 从左到右读进中序表达式的每个字符。

2. 如果读到的字符为操作数，则直接输出到后缀表达式中。

3. 如果遇到“)”，则弹出栈内的运算符，直到弹出到一个“(”,两者相互抵消。

4. “(”的优先级在栈内比任何运算符都小，任何运算符都可以压过它，不过在栈外却是优先级最高者。

5. 当运算符准备进入栈内时，必须和栈顶的运算符比较，如果外面的运算符优先级高于栈顶的运算符的优先级，则压栈；如果优先级低于或等于栈顶的运算符的优先级，则弹栈。直到栈顶的运算符的优先级低于外面的运算符优先级或者栈为空时，再把外面的运算符压栈。

6. 中缀表达式读完后，如果运算符栈不为空，则将其内的运算符逐一弹出，输出到后缀表达式中。

//比较lhs的优先级是否不高于rhs，rhs表示栈顶的符号
    bool priority(const char &lhs, const char &rhs)
    {
        if (rhs == '(')//左括号在栈外优先级最高
            return false;
        if (lhs == '+' || lhs == '-')
            return true;
        if ((lhs == '*' || lhs == '/') && (rhs == '*' || rhs == '/'))
            return true;
        return false;
    }
    //将中缀表达式转换成后缀式（逆波兰表达式）
    string exchange(const string &str)
    {
        vector<char> vec;
        string res;
        stack<char> st;//操作符堆栈
        for (int i = 0; i < str.size(); ++i)
        {
            if (isdigit(str[i]))//如果是数字，直接输出到后序表达式中
            {
                vec.push_back(str[i]);
            }
            else//如果是符号,需要与栈顶的元素进行比较
            {
                if (st.empty() || str[i] == '(')//小括号在栈外优先级最高，直接压栈
                    st.push(str[i]);
                else
                {
                    if (str[i] == ')')//遇到右括号，则弹栈，直到遇到左括号，两者相互抵消
                    {
                        while (!st.empty() && st.top() != '(')
                        {
                            vec.push_back(st.top());
                            st.pop();
                        }
                        st.pop();
                    }
                    else//遇到的是其他操作符
                    {
                        if (priority(str[i], st.top()))//优先级比栈顶元素低
                        {
                            while (!st.empty())
                            {
                                vec.push_back(st.top());
                                st.pop();
                            }
                            st.push(str[i]);
                        }
                        else//优先级比栈顶元素高，压栈
                        {
                            st.push(str[i]);
                        }
                    }
                }
            }
        }
        while (!st.empty())//如果堆栈不为空，则将其中的元素全部弹出
        {
            vec.push_back(st.top());
            st.pop();
        }
        for (auto v : vec)
            res += v;
        return res;
    }

**3、后缀表达式求值**

后缀表达式具有和前缀表达式类似的好处，没有优先级的问题。

1. 直接读取表达式，如果遇到数字就压栈。

2. 如果遇到运算符，就弹出两个数进行运算，随后再将运算结果压栈。

//定义四则运算
    int operate(int first, int second, char op)
    {
        int res = 0;
        switch (op)
        {
            case '+':
                res = first + second;
                break;
            case '-':
                res = first - second;
                break;
            case '*':
                res = first*second;
                break;
            case '/':
                res = first / second;
                break;
            default:
                break;
        }
        return res;
    }
    
    int calculate(string input)
    {
        stack<int> st;//操作数堆栈
        for (auto &s : input)
        {
            if (isdigit(s))//如果是数字就压栈
            {
                st.push(s - '0');
            }
            else//遇到字符就弹出两个操作数进行运算
            {
                int a = st.top();
                st.pop();
                int b = st.top();
                st.pop();
                st.push(operate(b, a, s));
            }
        }
        return st.empty() ? 0 : st.top();//最后的结果为栈顶元素
    }
    
    int main(int argc, char const *argv[])
    {
        string str = "1+(3+4)*5-2";
        cout << exchange(str) << endl;
        cout << calculate(exchange(str)) << endl;
        system("pause");
        return 0;
    }

本文转载于：https://blog.csdn.net/daaikuaichuan/article/details/80315261