当前位置:首页 > 编程 > 算法 > 正文内容

算法_逆波兰表达式求值

七星4年前 (2020-05-16)算法1633

题目:

根据逆波兰表示法,求表达式的值.

有效的运算符包括: +  -  *  /

每个运算对象可以是整数, 也可以是另一个逆波兰表达式.




说明:

  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 21 + 21 2 +
+ 2 * 3 42 + 3 * 42 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();
    }
}




排错:

写完代码,去执行了一下,发现报错了.报错了是好事,让我们知道自己的薄弱点

但是这个报错很迷茫:

image.png

他说第60行代码报错,string类型的"/"不能存在栈里面,

下面是我的第60行代码.

image.png

我寻思着,我也没让你存啊.群友告诉我说,case要加break.嗯,加.

果然,加完就不报错了:

image.png

至于为什么要加break,去看了网上的一些解释,这里放一下我自己的理解:

switch是判断,判断完成后,会jmp到符合条件的case的内存位置.

然后代码依次执行,case本身不具备jmp到switch之外的指令,

所以当一个case执行完之后,会继续执行下一个case,直到遇到break,才会jmp出switch.

break从汇编的角度讲,就是jmp到一个循环(判断)结束时的内存地址.


其实写到这里,我有个问题,为什么case不自带jmp呢?

从网上找来了个例子:

image.png

image.png

image.png

image.png


image.png


转载请声名出处|qixingbit.com

相关文章

算法_合并两个有序链表

算法_合并两个有序链表

认识链表:链表是一种物理存储单元上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点(链表中每一个元素称为结点)组成,结点可以在运行时动态生成。每个结点包括...

发表评论

访客

看不清,换一张

◎欢迎参与讨论,请在这里发表您的看法和观点。