LeetCode 150. 逆波兰表达式求值

比眉伴天荒 2022-11-11 13:27 192阅读 0赞

根据 逆波兰表示法，求表达式的值。

有效的算符包括 +、-、\*、/ 。每个运算对象可以是整数，也可以是另一个逆波兰表达式。

说明：

*  整数除法只保留整数部分。 给定逆波兰表达式总是有效的。换句话说，表达式总会得出有效数值且不存在除数为 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
     
    
    提示：
    
    1 <= tokens.length <= 104
    tokens[i] 要么是一个算符（"+"、"-"、"*" 或 "/"），要么是一个在范围 [-200, 200] 内的整数
    
    来源：力扣（LeetCode）
    链接：https://leetcode-cn.com/problems/evaluate-reverse-polish-notation
    著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路：我们可以知道逆波兰表达式的运算符号前的两个数值便是该运算式的数值，即例如3,4，+，那么其真正运算即为3+4，而无需考虑运算的优先级等，所以可以利用栈来进行逆波兰表达式直接求值。具体思路如下：

1.  创建数值栈来存储每一个数值；
2.  对于输入的字符串的内容，判断其是数值还是运算符号；
3.  若是数值，则直接将字符串转化为数值，并将数值放入数值栈中；
4.  若是运算符号，则弹出栈顶的两个数值，对其使用运算符号进行运算，结果压回栈内；
5.  回到第二个步骤，直到输入的字符串遍历完毕；
6.  由于题目保证输入的合法性和结果的正确性，所以最后数值栈一定只会剩下一个数值，这个数值也是最终的结果，将其从栈顶弹出，返回到结果即可解出题目。

class Solution {
        
        public int evalRPN(String[] tokens) {
        
            Stack<Integer> numStack=new Stack<Integer>();
            for(String token:tokens) {
        
            	if(isNum(token)) {
        
            		numStack.push(Integer.parseInt(token));
            	}else {
        
            		int num1=numStack.pop();
            		int num2=numStack.pop();
            		if(token.equals("+")) {
        
            			numStack.push(num1+num2);
            		}else if(token.equals("-")) {
        
            			numStack.push(num2-num1);
            		}else if(token.equals("*")) {
        
            			numStack.push(num1*num2);
            		}else {
        
    					numStack.push(num2/num1);
    				}
            	}
            }
            return numStack.pop();
        }
    	
    	public boolean isNum(String token) {
        
    		if(Character.isDigit(token.charAt(token.length()-1))) return true;
    		else return false;
    	}
    }