【LeetCode】-- 150. 逆波兰表达式求值

简介: 【LeetCode】-- 150. 逆波兰表达式求值

1. 题目

150. 逆波兰表达式求值 - 力扣(LeetCode)

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

注意:两个整数之间的除法只保留整数部分。可以保证给定的逆波兰表达式总是有效的。换句话说,表达式总会得出有效数值且不存在除数为 0 的情况。

2. 示例

示例 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 + 2 ) * ( 3 + 4 ) 。该算式的逆波兰表达式写法为 ( ( 1 2 + ) ( 3 4 + ) * ) 。

逆波兰表达式主要有以下两个优点:

(1)去掉括号后表达式无歧义,上式即便写成 1 2 + 3 4 + * 也可以依据次序计算出正确结果。

(2)适合用栈操作运算:遇到数字则入栈;遇到算符则取出栈顶两个数字进行计算,并将结果压入栈中

3. 分析

(1)平时用的表达式都是中缀表达式,根据栈的性质,表达式中,会有以下两种情况:

       ①当遇到操作数时就入栈

       ②当遇到操作符就把栈顶数据拿出来和操作符后面的数据进行运算,运算结果再入栈

(2)但是中缀转后缀表达式和中缀表达式不同的就是调整运算符的优先级

       如果是操作数,直接入栈

       如果是操作符,从栈里连续取出两个操作数进行计算,并将结果入栈

 

(3)代码给定的入参是vector不是string,因为不知道一个操作数有几个项,得用特殊符号比如空格去分割,而示例每项都是一个字符串,vector的类型是string就更方便获取表达式的每一个元素

4. 代码实现

1. class Solution {
2. public:
3. 
4. //取左操作数和右操作数
5. void getOPNum(stack<int>& st,int& left,int& right)
6.     {
7.         right = st.top();
8.         st.pop();
9.         left = st.top();
10.         st.pop();
11.     }
12. 
13. int evalRPN(vector<string>& tokens) {
14.         stack<int> st; 
15. for(const auto& ch:tokens)//为了防止tokens发生深拷贝,用&
16.         {
17. 
18. int left,right;//左右操作数
19. 
20. //遇到操作符就取栈顶两个操作数
21. //遇到操作数就直接入栈
22. switch(ch.back())//switch要求括号内容是整型,因此入栈的ch要转为整型,只有操作数需要转,操作符不需要处理
23.             {
24. case '+':
25. getOPNum(st,left,right);//取取栈顶两个操作数
26.                     st.push(left+right);//将计算结果入栈
27. break;
28. case '-':
29. getOPNum(st,left,right);
30.                     st.push(left-right);
31. break;
32. case '*':
33. getOPNum(st,left,right);
34.                     st.push(left*right);
35. break;
36. case '/':
37. getOPNum(st,left,right);
38.                     st.push(left/right);
39. break;
40. default://遇到操作数就直接入栈
41.                     st.push(stoi(ch));//入栈的操作数必须转为整形
42. break;
43.             }
44.         }
45. 
46. return st.top();//返回栈顶数据
47.     }
48. };


相关文章
|
10天前
|
算法 Go
golang力扣leetcode 399.除法求值
golang力扣leetcode 399.除法求值
29 0
|
10天前
leetcode代码记录(逆波兰表达式求值
leetcode代码记录(逆波兰表达式求值
14 0
|
10天前
|
存储 人工智能 BI
leetcode 399 除法求值
leetcode 399 除法求值
14 1
|
10天前
|
Java
LeetCode题解-逆波兰表达式求值-Java
逆波兰表达式求值-Java
17 0
|
10天前
|
Go
golang力扣leetcode 150.逆波兰表达式求值
golang力扣leetcode 150.逆波兰表达式求值
23 0
|
10天前
|
存储 算法 vr&ar
☆打卡算法☆LeetCode 150. 逆波兰表达式求值 算法解析
☆打卡算法☆LeetCode 150. 逆波兰表达式求值 算法解析
|
6月前
|
算法
代码随想录算法训练营第十一天 | LeetCode 20. 有效的括号、LeetCode 1047. 删除字符串中的所有相邻重复项、LeetCode 150. 逆波兰表达式求值
代码随想录算法训练营第十一天 | LeetCode 20. 有效的括号、LeetCode 1047. 删除字符串中的所有相邻重复项、LeetCode 150. 逆波兰表达式求值
41 0
|
1天前
|
算法 索引
力扣刷题【第一期】
这是一个关于算法的总结,包含7个不同的问题。1)爬楼梯问题,使用动态规划,通过迭代找到到达n阶楼梯的不同方法数。2)两数之和,通过双重循环找出数组中和为目标值的两个数的索引。3)移动零,使用双指针将数组中的0移到末尾。4)合并有序链表,创建新链表按升序合并两个链表。5)删除链表重复值,遍历链表删除重复元素。6)环形链表检测,使用快慢指针判断链表是否有环。7)相交链表,计算链表长度找
6 1
|
1天前
|
存储 Java
JAVA数据结构刷题 -- 力扣二叉树
JAVA数据结构刷题 -- 力扣二叉树
7 0