算法_逆波兰表达式求值
题目:
根据逆波兰表示法,求表达式的值.
有效的运算符包括: + - * /
每个运算对象可以是整数, 也可以是另一个逆波兰表达式.
说明:
1.整数除法只保留整数部分.
2.给定逆波兰表达式总是有效的.也就是说,表达式总会得出有效值且不存在除数为0的情况.
eg1:
输入:["2","1","+","3","*"]
输出:9
解释:((2+1)*3) = 9
eg2:
输入:["4","13","5","/","+"]
输出:6
解释:(4+(13/5)) = 6
四则运算
这里说明一下四则运算. 四则运算分为三种:
1.前缀表达式(prefix expression),又称波兰表达式.
2.中缀表达式(infix expression)
3.后缀表达式(postfix expression),又称逆波兰表达式
eg:
前缀表达式 | 中缀表达式 | 后缀表达式 |
+ 1 2 | 1 + 2 | 1 2 + |
+ 2 * 3 4 | 2 + 3 * 4 | 2 3 4 * + |
+ 9 * - 4 1 2 | 9 + (4 - 1) * 2 | 9 4 1 - 2 * + |
解读:
1.中缀表达式是我们最熟悉的表达式,不做解释.
2.在前缀表达式中,"+"的意思是,它之后的两个数相加;"*"是它之后的两个数相乘."-","/"和加乘一样.
在" + 9 * - 4 1 2 "这个式子中,+后面的两个数是 "9" 和 "* - 4 1 2".然后是*,它后面的两个数是" - 4 1 "和"2".然后-,就是4-1.
最后这个式子变成了:9 + (4 - 1) * 2.
3.后缀表达式和前缀类似, 只不过把运算符放到了两个运算数之后了. 可以仔细观察上面的eg.
解题思路及过程:
思路:首先拿到数组,需要遍历数组.每当遇到一个运算符时,需要让符号之前的两个值运算(最后遍历的值最先参与运算,就像是栈,数据先进后出).
所以只要遍历到运算数就让这个数存入栈中,当遇到运算符时,将栈顶的两个值pop出来运算,再将运算结果push到栈中.
过程:
1. 写一个eval()方法,要求方法传入题目数组(String[] tokens).
//参数:传入题目数组 public int eval(String[] tokens){ }
2. 遍历数组.将tokens中的每一个值放入token中.
for(String token : tokens){ }
3. 调用isOperator()方法判断token是否为字符.
private boolean isOperator(String token){ return "+-*/".contains(token); }
返回False,将这个整数(Integer.parseInt(tokens))入栈(stack.push()).
Stack<Integer> stack = new Stack<Integer>(); stack.push(Integer.parseInt(token));
返回True
1>.将栈顶两个数取出(stack.pop())
int right = stack.pop(); //运算符右边的数 int lift = stack.pop(); //运算符左边的数
2>.调用calculate()方法运算
private int calculate(int lift, int right, String operator) { switch (_operator) { case "+" : return lift + right; case "-" : return lift - right; case "*" : return lift * right; default : return lift / right; } }
3>.再将结果(calculate(lift, right, operator))压入栈中.
stack.push(calculate(lift, right, operator));
4.得到结果
return stack.pop();
算法代码:
import java.util.Stack; public class _001_InversePolishEvaluationExpression{ private boolean isOperator(String token){ return "+-*/".contains(token); } private int calculate(int lift, int right, String operator){ switch (operator){ case "+" : return lift + right; case "-" : return lift - right; case "*" : return lift * right; default : return lift / right; } } //String[] :题目 public int eval(String[] tokens){ Stack<Integer> stack = new Stack<Integer>(); if( isOperator(token) ) {//如果是运算符 int lift = stack.pop(); //运算符左边的数 String operator = token;//运算符 stack.push(calculate(lift, right, operator)); }else {//如果是数字 stack.push(Integer.parseInt(token)); } return stack.pop(); } }
代码优化:
优化1.取出值,运算完再将结果压入栈中:
原代码:
int right = stack.pop(); //运算符右边的数 int lift = stack.pop(); //运算符左边的数 String operator = token;//运算符 stack.push(calculate(lift, right, operator));
优化后:
stack.push(calculate(stack.pop(),stack.pop(), token));
注意:
栈顶的数据是运算符右边的数据,所以最先取出的是right,在接收参数的时候需要将
calculate(int lift, int right, String operator) 改为
calculate(int right, int lift, String operator)
优化2. if语句的优化:
if(isOperator(token)) {//运算符 stack.push(calculate(stack.pop(),stack.pop(), token)); }else {//数字 stack.push(Integer.parseInt(token)); }
可以发现,这个判断都在push数据,所以可以写成:
stack.push( isOperator(token)? calculate(stack.pop(),stack.pop(),token) : Integer.parseInt(token) );
优化3. 判断字符优化:
从代码逻辑可以看出,字符判断做了两次,第一次是判断"我是不是",第二次判断是"我是哪一个":
stack.push( isOperator(token)? calculate(stack.pop(),stack.pop(),token) : Integer.parseInt(token) );
对于这两次判断,从逻辑结构来看的话,可以写成两次,但是从优化的角度来说,完全可以做一次.
所以两次判断直接可以写成一个,"我要干啥":
switch (token) { case "+" : stack.push(stack.pop() + stack.pop()); case "*" : stack.push(stack.pop() * stack.pop()); case "-" : stack.push(- stack.pop() + stack.pop()); case "/" : int right = stack.pop(); stack.push(stack.pop() / right); default : stack.push(Integer.parseInt(token)); }
因为第一个取出来的数是右操作数,所以在做除法的时候,需要定义个变量去接收第一个取出的数.
至于为什么减法这么添"-"号,请自行体会.
然后可以删除两个不需要的方法.
最终代码:
import java.util.Stack; public class _001_InversePolishEvaluationExpression{ public int eval(String[] tokens){ Stack<Integer> stack = new Stack<Integer>(); for(String token : tokens) { switch (token) { case "+" : stack.push(stack.pop() + stack.pop()); case "*" : stack.push(stack.pop() * stack.pop()); case "-" : stack.push(- stack.pop() + stack.pop()); case "/" : int right = stack.pop(); stack.push(stack.pop() / right); default : stack.push(Integer.parseInt(token)); } } return stack.pop(); } }
排错:
写完代码,去执行了一下,发现报错了.报错了是好事,让我们知道自己的薄弱点
但是这个报错很迷茫:
他说第60行代码报错,string类型的"/"不能存在栈里面,
下面是我的第60行代码.
我寻思着,我也没让你存啊.群友告诉我说,case要加break.嗯,加.
果然,加完就不报错了:
至于为什么要加break,去看了网上的一些解释,这里放一下我自己的理解:
switch是判断,判断完成后,会jmp到符合条件的case的内存位置.
然后代码依次执行,case本身不具备jmp到switch之外的指令,
所以当一个case执行完之后,会继续执行下一个case,直到遇到break,才会jmp出switch.
break从汇编的角度讲,就是jmp到一个循环(判断)结束时的内存地址.
其实写到这里,我有个问题,为什么case不自带jmp呢?
从网上找来了个例子: