Day75 逆波兰表达式求值

时间:2021-7-3 作者:qvyue

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

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

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

示例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[i] 要么是一个算符(”+”、”-“、”*” 或 “/”),要么是一个在范围 [-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 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();
    }
}
Day75 逆波兰表达式求值
image

官方解

https://leetcode-cn.com/problems/evaluate-reverse-polish-notation/solution/ni-bo-lan-biao-da-shi-qiu-zhi-by-leetcod-wue9/

  1. 即我的解法

    • 时间复杂度:O(n)
    • 空间复杂度:O(n)
  2. 数组模拟栈

声明:本文内容由互联网用户自发贡献自行上传,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任。如果您发现有涉嫌版权的内容,欢迎发送邮件至:qvyue@qq.com 进行举报,并提供相关证据,工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。