LetCode: 150. 逆波兰表达式求值

秒速五厘米 2022-05-04 09:27 193阅读 0赞

# 提示 #

LintCode中的相关算法题实现代码，可以在我的[GithHub][]中下载。

# 题目需求 #

根据[逆波兰表示法][Link 1]，求表达式的值。

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

**说明：**

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

# 结题思路 #

使用栈结构

# 实现代码 #

/**
     * locate com.hust.edu.stack
     * Created by mastertj on 2018/10/22.
     * 150. 逆波兰表达式求值
     */
    public class _150_EvalRPN {
        public int evalRPN(String[] tokens) {
            Stack<Integer> stack=new Stack<>();
            for(int i=0; i< tokens.length;i++){
                String token = tokens[i];
                switch (token) {
                    case "+":
                        stack.push(stack.pop()+stack.pop());
                        break;
                    case "-":
                        Integer n1=stack.pop();
                        Integer n2=stack.pop();
                        stack.push(n2-n1);
                        break;
                    case "*":
                        stack.push(stack.pop()*stack.pop());
                        break;
                    case "/":
                        Integer num1=stack.pop();
                        Integer num2=stack.pop();
                        stack.push(num2/num1);
                        break;
                    default:
                        stack.push(Integer.valueOf(token));
                        break;
                }
            }
            return stack.pop();
        }
        public static void main(String[] args) {
    
        }
    }

[GithHub]: https://github.com/Tjcug/LeetCode
[Link 1]: https://baike.baidu.com/item/%E9%80%86%E6%B3%A2%E5%85%B0%E5%BC%8F/128437