剑指offer系列——剑指 Offer II 036. 后缀表达式(逆波兰表达式)
⭐️前面的话⭐️
大家好!本篇文章将介绍的剑指offerOJ题,来自力扣[剑指 Offer II 036. 后缀表达式],本文将以这道题为背景,介绍后缀表达式,展示代码语言暂时为:Java
📒博客主页:未见花闻的博客主页
🎉欢迎关注🔎点赞👍收藏⭐️留言📝
📌本文由未见花闻原创!
📆华为云首发时间:🌴2022年4月30日🌴
✉️坚持和努力一定能换来诗与远方!
💭参考书籍:📚《C语言程序设计》📚《剑指offer》
💬参考在线编程网站:🌐牛客网🌐力扣
博主的码云gitee,平常博主写的程序代码都在里面。
博主的github,平常博主写的程序代码都在里面。
🍭作者水平很有限,如果发现错误,一定要及时告知作者哦!感谢感谢!
⭐️剑指 Offer II 036. 后缀表达式⭐️
🔐题目详情
根据 逆波兰表示法,求表达式的值。
有效的算符包括 +、-、*、/ 。每个运算对象可以是整数,也可以是另一个逆波兰表达式。
说明:
整数除法只保留整数部分。
给定逆波兰表达式总是有效的。换句话说,表达式总会得出有效数值且不存在除数为 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
提示:
tokens[i]
要么是一个算符("+"、"-"、"*" 或 “/”),要么是一个在范围[-200, 200]
内的整数
来源:力扣(LeetCode)链接:剑指 Offer II 036. 后缀表达式 |
---|
💡解题思路
预备知识:
我们常用的数学加减乘除运算表达式都是中缀表达式,比如
,将中缀表达式按运算顺序打上不同的的括号对,分别将运算符移到对应括号最右边,再将所有括号擦除,就能得到后缀表达式,同理将运算符移到到对应括号最左边就是前缀表达式。
逆波兰表达式:
逆波兰表达式是一种后缀表达式,所谓后缀就是指算符写在后面。
- 平常使用的算式则是一种中缀表达式,如
( 1 + 2 ) * ( 3 + 4 )
。 - 该算式的逆波兰表达式写法为
( ( 1 2 + ) ( 3 4 + ) * )
。
逆波兰表达式主要有以下两个优点:
- 去掉括号后表达式无歧义,上式即便写成
1 2 + 3 4 + *
也可以依据次序计算出正确结果。 - 适合用栈操作运算:遇到数字则入栈;遇到算符则取出栈顶两个数字进行计算,并将结果压入栈中。
解题思路:
适合用栈操作运算:遇到数字则入栈;遇到运算符则取出栈顶两个数字进行计算,并将结果压入栈中。
首先遍历字符串数组,然后判断元素是否是运算符,如果是则从栈中取出两个元素进行运算,并将结果入栈,如果不是运算符则将字符串转数字入栈。
注意,先出栈的数要放在运算符右边,后出栈的数放在运算符左边。
最终栈顶元素的值即为运算结果。
比如:
,转换成中缀表达式为
,结果为
。
🔑源代码
Java:
class Solution {
public int evalRPN(String[] tokens) {
Stack<Integer> stack = new Stack<>();
for (int i = 0; i < tokens.length; i++) {
String s = tokens[i];
if (isOperation(s)) {
//遇到运算符,出栈元素,进行计算,结果入栈
int num2 = stack.pop();
int num1 = stack.pop();
switch (s) {
case "+":
stack.push(num1 + num2);
break;
case "-":
stack.push(num1 - num2);
break;
case "*":
stack.push(num1 * num2);
break;
case "/":
stack.push(num1 / num2);
break;
}
} else {
//遇到数字,入栈,等待计算
stack.push(Integer.parseInt(s));
}
}
//最终栈中的元素为最终结果
return stack.pop();
}
public boolean isOperation(String s) {
if (s.equals("+") || s.equals("-") || s.equals("*") || s.equals("/")) {
return true;
}else {
return false;
}
}
}
🌱总结
我们常用的数学加减乘除运算表达式都是中缀表达式,比如
,将中缀表达式按运算顺序打上不同的的括号对,分别将运算符移到对应括号最右边,再将所有括号擦除,就能得到后缀表达式,同理将运算符移到到对应括号最左边就是前缀表达式。
首先遍历字符串数组,然后判断元素是否是运算符,如果是则从栈中取出两个元素进行运算,并将结果入栈,如果不是运算符则将字符串转数字入栈。
注意,先出栈的数要放在运算符右边,后出栈的数放在运算符左边。
最终栈顶元素的值即为运算结果。
类似题如下:
150. 逆波兰表达式求值
- 点赞
- 收藏
- 关注作者
评论(0)