提供了编程的基础技术教程

zl程序教程

您现在的位置是：首页 >  其他

当前栏目

逆波兰表达式求值

2023-03-15 23:26:39 时间

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

[https://leetcode-cn.com/problems/evaluate-reverse-polish-

notation/](https://links.jianshu.com/go?to=https%3A%2F%2Fleetcode-

cn.com%2Fproblems%2Fevaluate-reverse-polish-notation%2F)

示例1：

输入：tokens = "2","1","+","3","*"undefined 输出：9undefined 解释：该算式转化为常见的中缀算术表达式为：((2 + 1) * 3) = 9

示例2：

输入：tokens = "4","13","5","/","+"undefined 输出：6undefined 解释：该算式转化为常见的中缀算术表达式为：(4 + (13 / 5)) = 6

示例3：

输入：tokens = "10","6","9","3","+","-11"," ","/"," ","17","+","5","+"undefined 输出：22undefined 解释：undefined 该算式转化为常见的中缀算术表达式为：undefined ((10 (6 / ((9 + 3) -11))) + 17) + 5undefined = ((10 (6 / (12 -11))) + 17) + 5undefined = ((10 (6 / -132)) + 17) + 5undefined = ((10 0) + 17) + 5undefined = (0 + 17) + 5undefined = 17 + 5undefined = 22

提示：

1 <= tokens.length <= 104undefined tokensi 要么是一个算符（"+"、"-"、"*" 或 "/"），要么是一个在范围 -200, 200 内的整数

Java解法

思路：

逆波兰表示法就是为了让计算机方便计算使用的，本身就是通过用栈来存储操作数，遇到运算符进行弹出操作数运算再入栈，直到结束 注意踩坑，出栈时的操作数，先出的是被操作的，注意位置顺序

package sj.shimmer.algorithm.m4_2021;
import java.util.Stack;
/**
 * Created by SJ on 2021/4/12.
 */
class D75 {
    public static void main(String[] args) {
//        System.out.println(evalRPN(new String[]{"2","1","+","3","*"}));
        System.out.println(evalRPN(new String[]{"4","13","5","/","+"}));
    }
    public static int evalRPN(String[] tokens) {
        Stack<Integer> stack = new Stack<>();
        for (String token : tokens) {
            Integer a = 0;
            Integer b = 0;
            switch (token) {
                case "+":
                    b = stack.pop();
                    a = stack.pop();
                    stack.add(a + b);
                    break;
                case "-":
                    b = stack.pop();
                    a = stack.pop();
                    stack.add(a - b);
                    break;
                case "*":
                    b = stack.pop();
                    a = stack.pop();
                    stack.add(a * b);
                    break;
                case "/":
                    b = stack.pop();
                    a = stack.pop();
                    stack.add(a / b);
                    break;
                default:
                    stack.add(Integer.parseInt(token));
                    break;
            }
        }
        return stack.pop();
    }
}

image

官方解

[https://leetcode-cn.com/problems/evaluate-reverse-polish-

notation/solution/ni-bo-lan-biao-da-shi-qiu-zhi-by-leetcod-

wue9/](https://links.jianshu.com/go?to=https%3A%2F%2Fleetcode-

cn.com%2Fproblems%2Fevaluate-reverse-polish-notation%2Fsolution%2Fni-bo-lan-

biao-da-shi-qiu-zhi-by-leetcod-wue9%2F)

  1. 栈

即我的解法

* 时间复杂度：O(n)
* 空间复杂度：O(n)数组模拟栈

相关文章