栈｜ Leetcode 150

Leetcode 分类刷题 —— 栈（Stack）

1、题目描述：

Leetcode 150. Evaluate Reverse Polish Notation 逆波兰表达式求值

You are given an array of strings tokens that represents an arithmetic expression in a Reverse Polish Notation. Evaluate the expression. Return an integer that represents the value of the expression.

给你一个字符串数组 tokens ，表示一个根据 逆波兰表示法 表示的算术表达式。 请你计算该表达式。返回一个表示表达式值的整数。

• 什么是逆波兰表达式

2、解题思路：

使用一个栈来保存操作数。
遍历表达式中的每个token：
如果token是操作符，则弹出栈顶的两个操作数，进行相应的操作，然后将结果压入栈中；
如果token是操作数，则将其转换为整数并将其压入栈中；
最终栈中只会剩下一个元素，即为表达式的计算结果。

3、代码

public int evalRPN(String[] tokens) {
    // 创建一个栈用于保存操作数
    Stack<Integer> stack = new Stack<>();
    // 遍历表达式中的每个token
    for (String token : tokens) {
        // 如果token是一个操作符，则弹出栈顶的两个操作数，并将它们执行相应的操作
        if (token.equals("+")) {
            int operand2 = stack.pop();
            int operand1 = stack.pop();
            stack.push(operand1 + operand2);
        } else if (token.equals("-")) {
            int operand2 = stack.pop();
            int operand1 = stack.pop();
            stack.push(operand1 - operand2);
        } else if (token.equals("*")) {
            int operand2 = stack.pop();
            int operand1 = stack.pop();
            stack.push(operand1 * operand2);
        } else if (token.equals("/")) {
            int operand2 = stack.pop();
            int operand1 = stack.pop();
            stack.push(operand1 / operand2);
        } else {
            // 如果token是一个操作数，则将其转换为整数并将其压入栈中
            stack.push(Integer.parseInt(token));
        }
    }
    // 最终栈中只会剩下一个元素，即为表达式的计算结果
    return stack.pop();
}