java:逆波兰表示法（后缀表达式）

待我称王封你为后i 2022-06-17 01:09 203阅读 0赞

用逆波兰表示法计算算术表达式的值。

有效运算符为+，-，\*，/。每个操作数可以是整数或另一个表达式。

例子：

["2", "1", "+", "3", "*"] -> ((2 + 1) * 3) -> 9
    
     ["4", "13", "5", "/", "+"] -> (4 + (13 / 5)) -> 6

public class Solution(){
     public int evalRPN(String[] tokens){
      //在这里写上你的代码
    }
    }

> 【知识点】：利用栈。  
> 从左到右遍历表达式的每个数字和符号，遇到是数字就进栈，遇到是符号，就将处于栈顶两个数字出栈，进行运算，运算结果进栈（结果取代参与运算的两个数字），一直到最终获得结果。

//代码语言组织
    /**1.需要创建一个存放整数的栈：**/
    import java.util.Stack;
    Stack<Integer>stack = new Stack<Integer>();
    
    /**2.要将String类型的数组tokens里的元素进栈**/
     for(int i=0;i<tokens.length();i++){
       int num=Integer.parseInt(tokens[i]);
       stack.add(num);
    }
    
    /**3.但我们知道第二步的代码会有报错的，当tokens数组里包含非数字元素时。 因为该 String 不能作为 int 分析，则抛出NumberformatException异常。所以我们可以利用这一点做一个异常处理**/
       for(int i=0;i<tokens.length();i++){
       try{
       int num=Integer.parseInt(tokens[i]);
       stack.add(num);}
       catch(Exception e){
       }
    }
    
    /**4.最后再在catch里写一个方法做计算的处理**/
    catch(Exception e){
    //取栈顶元素出来运算
      int a=stack.pop();
      int b=stack.pop();
      calculte(a,b,tokens[i]);
    
       }
    public int calculate(){
      switch(opera){
          case "+":return a+b;
          case "-":return a-b;
          case "*":return a*b;
          case "/":return a/b;
          default:return 0;
      }
    }

但是！！这个代码并没有通过所有测试用例

> 不通过 您的代码已保存 答案错误:您提交的程序没有通过所有的测试用例 case通过率为5.88%
> 
> 测试用例: \[“0”,”3”,”/”\]
> 
> 对应输出应该为:
> 
> 0
> 
> 你的输出为:
> 
> java.lang.ArithmeticException: / by zero

**所以还要再考虑一个除0的情况**

//解决了除0的情况
    case "/":
    try{
       return a/b;}
    catch(Exception e){
              return 0;
          }

但是最后，也并没通过

> 测试用例: \[“3”,”4”,”-“\]
> 
> 对应输出应该为:
> 
> 1
> 
> 你的输出为:  
> \-1  
> 这时我想明白了，之所以代码不通过，不是我没有考虑除0的情况。是因为在运算中乘法和加分不在乎操作数的顺序，而减法和除法却要考虑顺序。有些可以通过就是因为乘法和加法不考虑顺序。  
> 好好想想，逆波兰表示法是从左到右遍历，所以【结果】=【左边数字】（符号）【右边数字】  
> 所以代码要这么改

case "+":return b+a;
    case "-":return b-a;
    case "-":return b-a;
    case "/":return b/a;

**AC代码：**

import java.util.*;
    public class Solution {
        public int evalRPN(String[] tokens) {
            //后缀表达式
            //建栈
       Stack<Integer>stack=new   Stack<Integer>();
         for(int i=0;i<tokens.length;i++){
           try{
           int num=Integer.parseInt(tokens[i]);
           stack.add(num);}
           catch(Exception e){
            //取栈顶元素(出栈)
              int a=stack.pop();
              int b=stack.pop();
              //calculate(a,b,tokens[i]);
              stack.add(calculate(a,b,tokens[i]));
          }
       }
       //到最后栈里只剩一个元素，所以取栈顶就可以
       return stack.pop();     
        }
        public int calculate(int a,int b,String opera){
          switch(opera){
    
          case "+":return b+a;
          case "-":return b-a;
          case "*":return b*a;
          case "/":return b/a;
          default:return 0;
      }
    
    }

![这里写图片描述][SouthEast]

[SouthEast]: /images/20220617/b94ed3eb19a04fb2bac6ad0da41327e9.png