leetcode150-逆波兰表达式求值

原题

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

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

说明:

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

解法

思想

最底层必是一个能运算的最小单元,只要将后序遍历的结果依次入栈,遇到一个运算符则让两个数字出栈,计算结果之后再将结果入栈,如此循环最后就能得到答案。

逆波兰表达式

代码

class Solution {
    public int evalRPN(String[] tokens) {
        Stack<Integer> stack = new Stack<>();
        for(String i:tokens){
            if(i.equals("+")){
                int num1 = Integer.valueOf(stack.pop());
                int num2 = Integer.valueOf(stack.pop());
                stack.push(num1+num2);
            }else if(i.equals("-")){
                int num1 = Integer.valueOf(stack.pop());
                int num2 = Integer.valueOf(stack.pop());
                stack.push(num2-num1);
            }else if(i.equals("*")){
                int num1 = Integer.valueOf(stack.pop());
                int num2 = Integer.valueOf(stack.pop());
                stack.push(num1*num2);
            }else if(i.equals("/")){
                int num1 = Integer.valueOf(stack.pop());
                int num2 = Integer.valueOf(stack.pop());
                stack.push(num2/num1);
            }else{
                stack.push(Integer.valueOf(i));
            }
        }
        return stack.peek();
    }
}

原创文章,作者:彭晨涛,如若转载,请注明出处:https://www.codetool.top/article/leetcode150-%e9%80%86%e6%b3%a2%e5%85%b0%e8%a1%a8%e8%be%be%e5%bc%8f%e6%b1%82%e5%80%bc/

(0)
彭晨涛彭晨涛管理者
上一篇 2019年12月11日
下一篇 2019年12月13日

相关推荐

  • leetcode378-有序矩阵中第K小的元素

    原题 给定一个 n x n 矩阵,其中每行和每列元素均按升序排序,找到矩阵中第k小的元素。请注意,它是排序后的第k小元素,而不是第k个元素。 示例: matrix = [ &nbs…

    算法 2020年2月14日
    0430
  • leetcode135-分发糖果

    原题 老师想给孩子们分发糖果,有 N 个孩子站成了一条直线,老师会根据每个孩子的表现,预先给他们评分。 你需要按照以下要求,帮助老师给这些孩子分发糖果: 每个孩子至少分配到 1 个…

    算法 2020年2月17日
    060
  • leetcode12-整数转罗马数字

    原题 罗马数字包含以下七种字符: I, V, X, L,C,D 和 M。 字符 数值 I 1 V 5 X 10 L 50 C 100 D 500 M 1000 例如, 罗马数字 2…

    算法 2020年2月29日
    070
  • leetcode7-整数反转

    原题 给出一个 32 位的有符号整数,你需要将这个整数中每位上的数字进行反转。 示例1: 输入: 123 输出: 321 示例2: 输入: -123 输出: -321 示例3: 输…

    算法 2020年2月26日
    0120
  • leetcode733-图像渲染

    原题 有一幅以二维整数数组表示的图画,每一个整数表示该图画的像素值大小,数值在 0 到 65535 之间。 给你一个坐标 (sr, sc) 表示图像渲染开始的像素值(行 ,列)和一…

    2019年12月13日
    0100
  • leetcode450-删除二叉搜索树中的节点

    原题 给定一个二叉搜索树的根节点 root 和一个值 key,删除二叉搜索树中的 key 对应的节点,并保证二叉搜索树的性质不变。返回二叉搜索树(有可能被更新)的根节点的引用。 一…

    2020年1月16日
    090
  • leetcode123-买卖股票的最佳时机III

    原题 给定一个数组,它的第 i 个元素是一支给定的股票在第 i 天的价格。 设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。 注意: 你不能同时参与多笔交易(你…

    算法 2020年6月16日
    01540
  • leetcode101-对称二叉树

    原题 给定一个二叉树,检查它是否是镜像对称的。 例如,二叉树 [1,2,2,3,4,4,3] 是对称的。     1  &nbsp…

    算法 2020年1月11日
    0120
  • leetcode18-四数之和

    原题 给定一个包含 n 个整数的数组 nums 和一个目标值 target,判断 nums 中是否存在四个元素 a,b,c 和 d ,使得 a + b + c + d 的值与 ta…

    算法 2020年5月5日
    0120
  • leetcode202-快乐数

    原题 编写一个算法来判断一个数是不是“快乐数”。 一个“快乐数”定义为:对于一个正整数,每一次将该数替换为它每个位置上的数字的平方和,然后重复这个过程直到这个数变为 1,也可能是无…

    算法 2019年12月18日
    0120

发表回复

登录后才能评论