LeetCode 150. Evaluate Reverse Polish Notation

题目描述

根据逆波兰表示法(后缀表达式),求表达式的值。

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

说明:

整数除法只保留整数部分。
给定逆波兰表达式总是有效的。换句话说,表达式总会得出有效数值且不存在除数为 0 的情况。

tag

基本计算器题 栈

样例

1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
12  
13  
14  
15  
16  
17  
18  
19  
20  
21  
22  
23  
输入: ["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  
  
来源:力扣(LeetCode)  
链接:https://leetcode-cn.com/problems/evaluate-reverse-polish-notation  
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。输入: ["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

(栈) O(n)
思路

一正一负取整时,先转换成都是正或都是负的情况,再加上符号。

复杂度分析:
python 代码
1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
12  
13  
14  
15  
16  
17  
18  
19  
20  
21  
22  
23  
24  
25  
26  
27  
28  
29  
class :  
    def evalRPN(self, tokens: List[str]) -> int:  
        stack = []  
        operations = {'+', '-', '*', '/'}  
          
        for token in tokens:  
              
            if token in operations:  
                right = stack.pop()  
                left = stack.pop()  
                  
                if token == '+':  
                    temp = left + right  
                elif token == '-':  
                    temp = left - right  
                elif token == '*':  
                    temp = left * right  
                else:  
                    if left * right >= 0:  
                        temp = left // right  
                    else:  
                        temp = -(-left // right)  
                      
                stack.append(temp)  
                  
            else:  
                stack.append(int(token))  
          
        return stack[0]  

—|—

糖果

糖果
LUA教程

Lapis框架的常用处理方法

Lapis框架的常用处理方法 Continue reading

MoonScript实现选择排序

Published on February 26, 2017

MoonScript与Redis客户端

Published on January 19, 2017