当前位置：首页 > news >正文

【LeetCode】【逆波兰表达式求解】

news 来源：原创 2024/5/19 5:02:52

150. 逆波兰表达式求值

根据逆波兰表示法，求表达式的值。

有效的算符包括 +、-、*、/ 。每个运算对象可以是整数，也可以是另一个逆波兰表达式。

注意两个整数之间的除法只保留整数部分。

可以保证给定的逆波兰表达式总是有效的。换句话说，表达式总会得出有效数值且不存在除数为 0 的情况。

示例 1：

输入：tokens = ["2","1","+","3","*"]
输出：9
解释：该算式转化为常见的中缀算术表达式为：((2 + 1) * 3) = 9
示例 2：

输入：tokens = ["4","13","5","/","+"]
输出：6
解释：该算式转化为常见的中缀算术表达式为：(4 + (13 / 5)) = 6
示例 3：

输入：tokens = ["10","6","9","3","+","-11","*","/","*","17","+","5","+"]
输出：22
解释：该算式转化为常见的中缀算术表达式为：
((10 * (6 / ((9 + 3) * -11))) + 17) + 5
= ((10 * (6 / (12 * -11))) + 17) + 5
= ((10 * (6 / -132)) + 17) + 5
= ((10 * 0) + 17) + 5
= (0 + 17) + 5
= 17 + 5
= 22

提示：

1 <= tokens.length <= 104
tokens[i] 是一个算符（"+"、"-"、"*" 或 "/"），或是在范围 [-200, 200] 内的一个整数

逆波兰表达式：

逆波兰表达式是一种后缀表达式，所谓后缀就是指算符写在后面。

平常使用的算式则是一种中缀表达式，如 ( 1 + 2 ) * ( 3 + 4 ) 。
该算式的逆波兰表达式写法为 ( ( 1 2 + ) ( 3 4 + ) * ) 。
逆波兰表达式主要有以下两个优点：

去掉括号后表达式无歧义，上式即便写成 1 2 + 3 4 + * 也可以依据次序计算出正确结果。
适合用栈操作运算：遇到数字则入栈；遇到算符则取出栈顶两个数字进行计算，并将结果压入栈中

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/evaluate-reverse-polish-notation
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

逆波兰表达式也就是后缀表达式。

我们一般写的a+b都是中缀表达式，也就是运算符在中间

而后缀表达式就是运算符在后面，也就是ab+

中缀表达式是不能进行运算的，因为优先级的问题，不能顺序进行运算，比方说1+2*3

后缀表达式的话就可以将1+2*3转换成1 2 3*+，因为它将运算符的优先级排出来了，所以可以让计算机直接顺序运算

后缀如何运算？

操作数的顺序不变，运算符按照优先级排序。

比防说我们的后缀表达式1 2 3*+

首先我们将操作数入栈，然后操作数就取连续两个栈顶数据运算，结果入栈

我们先将上面的后缀表达式中的1和2入栈，发现后面没有操作数，而是数字3，于是就接着入栈，然后发现后面是*，也就是操作数，我们就将栈连续出栈两个元素，也就是2和3出栈，然后进行乘法操作，运算出来的结果6再次入栈。然后我们接着读取，遇到了操作符+，然后我们再从我们的栈顶出两个元素1和6，进行加法操作，获得的结果7再次入栈，然后我们发现我们的后缀表达式已经读取完毕了，然后我们的栈中就是我们的计算结果。

class Solution {
public:
    int evalRPN(vector<string>& tokens) {

        //遍历tokens中的元素
        for(auto& str:tokens)
        {
            //如果是操作符就进行取操作数，然后进行运算的操作

            if(str=="+"||str=="-"||str=="*"||str=="/")
            {
                //注意，先取出来的是右操作数，然后取出来的是左操作数
                int right=st.top();
                st.pop();
                int left=st.top();
                st.pop();
            //switch-case中传入的不能是字符串string
                switch(str[0])
                {
                    case '+':
                        st.push(left+right);
                        break;
                    case '-':
                        st.push(left-right);
                        break;
                    case '*':
                        st.push(left*right);
                        break;
                    case '/':
                        st.push(left/right);
                        break;

                }
                
            }
            else
            {
                //如果是操作数的话就将其转换成数字然后入栈
                //stoi就是将字符串转换成int类型（string to int）
                st.push(stoi((str)));
            }
        }
        return st.top();
    }
private:
    //创建一个栈
    stack<int> st;
};

我们发现这样的话咱的int类型hold不住数据，在计算乘法的时候会崩掉的

所以哦我们将int全部都改成long long

class Solution {
public:
    int evalRPN(vector<string>& tokens) {

        //遍历tokens中的元素
        for(auto& str:tokens)
        {
            //如果是操作符就进行取操作数，然后进行运算的操作

            if(str=="+"||str=="-"||str=="*"||str=="/")
            {
                //注意，先取出来的是右操作数，然后取出来的是左操作数
                long long right=st.top();
                st.pop();
                long long left=st.top();
                st.pop();
            //switch-case中传入的不能是字符串string
                switch(str[0])
                {
                    case '+':
                        st.push(left+right);
                        break;
                    case '-':
                        st.push(left-right);
                        break;
                    case '*':
                        st.push(left*right);
                        break;
                    case '/':
                        st.push(left/right);
                        break;

                }
                
            }
            else
            {
                //如果是操作数的话就将其转换成数字然后入栈
                //stoll就是将字符串转换成longlong类型（string to long long）
                st.push(stoll((str)));
            }
        }
        return st.top();
    }
private:
    //创建一个栈
    stack<long long> st;
};

中缀表达式如何转换成后缀表达式？

中缀表达式：1+2*3

后缀表达式：1 2 3 * +

中缀转后缀就是要调节运算符的优先级

1.操作数输出

2.如果当前栈为空的操作符比操作符栈的栈顶的操作符的优先级更高，就入栈，

否则就说明新的操作符比操作符栈栈顶的优先级低或相等，也就是说明当前栈顶的操作符对应的运算可以执行

上面的12入数据栈，+入操作符栈，然后遇到*号，优先级比+高，就继续将3入数据栈，*入操作符栈。然后发现读取完毕了，就将23*取出，先进行运算，然后再将23*作为一整个结果压入数据栈，然后再取出1和+，和23*结合形成123*+，也就形成了后缀表达式

再举一个例子1+2*3/4+5-6

1和2如操作数栈，+如操作符栈，然后读取到*，优先级比+高，就如操作符栈，3也同时进入操作数栈，/和*的优先级相同，就说明2*3可以运行，就取出23*压入操作数栈，然后将4和/分别压入操作数栈和操作符栈，然后继续读取，发现+比/的优先级第，所以前面的/可以运行，就取出23*和4与操作符/构成23*4/，重新将这个结果压入操作数栈，然后向后读取的4与5之间的+与1+2之间的+优先级相同，就说明前面的1与2之间的+可以运算，然后就可以将1和23*4/进行加法运算，形成123*4/+然后5后面的-与45之间的+优先级相投，按照上面的操作形成123*4/+5+，然后后面的6也是以此类推，形成123*4/+56-

如果遇到括号怎么办？

1+(2+3)*4-5

1，+入操作数栈和操作符栈，然后遇到(的话，可以设置一个flag=true来表示遇到括号了。我们括号的优先级是最高的。也就是先将23+如操作数栈，然后遇到*号，优先级比+更高，所以形成23+4*压入操作数栈，后面的-与前面1后面的+的优先级相同，于是前面的+运算可以执行，也就是将123+4*+，然后再计算-5，也就是123+4*+5-，得到最终结果。