本題考察的是后綴（逆波蘭）表達式和棧的使用

題目描述

根據(jù)逆波蘭表示法，求表達式的值。

有效的運算符包括 +, -, *, / 。每個運算對象可以是整數(shù)，也可以是另一個逆波蘭表達式。

說明：
整數(shù)除法只保留整數(shù)部分。
給定逆波蘭表達式總是有效的。換句話說，表達式總會得出有效數(shù)值且不存在除數(shù)為 0 的情況。

示例 1：

輸入: ["2", "1", "+", "3", "*"]
輸出: 9
解釋: ((2 + 1) * 3) = 9

示例 2：

輸入: ["4", "13", "5", "/", "+"]
輸出: 6
解釋: (4 + (13 / 5)) = 6

示例 3：

輸入: ["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

題目思考

首先我們要知道什么是（后綴表達式，也就是波蘭逆表達式）。我們平時在進行二元操作符運行的時候用的都是中綴表達式，如2+3，如果轉(zhuǎn)化為后綴表達式就是23+，每個二元操作符都在他對應(yīng)的兩個數(shù)字的后面。更復(fù)雜一點的中綴表達式，如9+（3-1）*3+10/2，他的后綴表達式是9 3 1 - 3 * + 10 2 / +。所以，叫后綴表達式的原因，就是所有的二元運算符都在他所操作的兩個數(shù)字的后面。每一個二元運算符的兩個操作數(shù)都是他們前面直接相鄰的兩個數(shù)（或者運算符）。因此，解這道題可以用棧，遍歷表達式，遇到數(shù)字將數(shù)字存入棧中，遇到運算符將棧頂?shù)膬蓚€數(shù)字彈出，求取結(jié)果后將結(jié)果壓入棧中。知道遍歷完表達式。

代碼

public int evalRPN(String[] tokens) {
        Stack<Integer> stack=new Stack();
        for(int i=0;i<tokens.length;i++){
            int index="+-*/".indexOf(tokens[i]);   //判斷是運算符還是數(shù)字
                int i1;
                int i2;
                switch(index){
                    case 0:     //如果是運算符，進行相應(yīng)運算，將運算結(jié)果壓棧
                        i1=stack.pop();
                        i2=stack.pop();
                        stack.push(i1+i2);
                        break;
                    case 1:
                        i1=stack.pop();
                        i2=stack.pop();
                        stack.push(i2-i1);
                        break;
                    case 2:
                        i1=stack.pop();
                        i2=stack.pop();
                        stack.push(i1*i2);
                        break;
                    case 3:
                        i1=stack.pop();
                        i2=stack.pop();
                        stack.push(i2/i1);
                        break;
                    default:    //如果是數(shù)字，將該數(shù)字壓棧
                        stack.push(Integer.valueOf(tokens[i]));
                        break;
            }
        }
        if(stack.isEmpty()){   //返回結(jié)果
            return 0;
        }else{
            return stack.pop();   
        }
}

解法二

使用遞歸和搜索。從逆表達式的后面往前面計算，不斷表達式化簡，最終得到兩個數(shù)字相運算的結(jié)構(gòu)。

private int N =-1;
   public int evalRPN(String[] tokens) {
       
       if(N==-1){
           N=tokens.length-1;
       }
       String src=tokens[N--];
       char head=src.charAt(0);
       if(src.length()==1&&"+-*/".indexOf(head)!=-1){
           Integer N1=evalRPN(tokens);
           Integer N2=evalRPN(tokens);
           switch(src){
               case "+": return N1+N2;
               case "-": return N2-N1;
               case "*": return N1*N2;
               case "/": return N2/N1;
               default: Integer.valueOf(src);
           }
       }
       return Integer.valueOf(src);
   }