leetcode刷题：栈与队列05（逆波兰表达式求值）

150. 逆波兰表达式求值

力扣题目链接

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

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

说明：

整数除法只保留整数部分。
给定逆波兰表达式总是有效的。换句话说，表达式总会得出有效数值且不存在除数为 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    
  

栈操作：遇到数字就入栈，先出栈的是加数、减数、除数、乘数；后出栈的是被加数、被减数、被除数、被乘数。
遇到数字则入栈、遇到运算符则取出栈顶两个数字进行计算，再将结果压入栈中。

package com.programmercarl.stacks_queues;

import java.util.Stack;

/** * @ClassName EvalRPN * @Descriotion TODO * @Author nitaotao * @Date 2022/6/30 13:26 * @Version 1.0 **/
public class EvalRPN {
    
    public int evalRPN(String[] tokens) {
    
        Stack stack = new Stack();
        for (int i = 0; i < tokens.length; i++) {
    
            switch (tokens[i]) {
    
                case "+":
                    //加数
                    Integer num1 = Integer.valueOf((String) stack.pop());
                    //被加数
                    Integer num2 = Integer.valueOf((String) stack.pop());
                    stack.push(String.valueOf(num2 + num1));
                    break;
                case "-":
                    //减数
                    Integer num3 = Integer.valueOf((String) stack.pop());
                    //被减数
                    Integer num4 = Integer.valueOf((String) stack.pop());
                    stack.push(String.valueOf(num4 - num3));
                    break;
                case "*":
                    //乘数
                    Integer num5 = Integer.valueOf((String) stack.pop());
                    //被乘数
                    Integer num6 = Integer.valueOf((String) stack.pop());
                    stack.push(String.valueOf(num6 * num5));
                    break;
                case "/":
                    //除数
                    Integer num7 = Integer.valueOf((String) stack.pop());
                    //被除数
                    Integer num8 = Integer.valueOf((String) stack.pop());
                    stack.push(String.valueOf(num8 / num7));
                    break;
                default:
                    stack.push(tokens[i]);
            }
        }
        return Integer.valueOf((String) stack.pop());
    }
}

一遍AC，舒服。！