Evaluate Reverse Polish Notation
Total Accepted:5898Total
Submissions:31322My Submissions
Evaluate the value of an arithmetic expression inReverse Polish
Notation.
Valid operators are+
,-
,*
,/
.
Each operand may be an integer or another expression.
Some examples:
["2", "1", "+", "3", "*"] -> ((2 + 1) * 3) -> 9
["4", "13", "5", "/", "+"] -> (4 + (13 / 5)) -> 6
本题就是考查栈的应用。
注意细节,很容易过。 3星级的题目吧。
1 要push入结果
2 两个数的计算顺序不能错,否则答案错误
class Solution {
public:
int evalRPN(vector<string> &tokens)
{
if (tokens.size() < 1) return 0;
stack<int> stk;
for (int i = 0; i < tokens.size(); i++)
{
if (!isOperand(tokens[i])) stk.push(stoi(tokens[i]));
else
{
int b = stk.top();
stk.pop();
int a = stk.top();
stk.pop();
int result = evaluate(a, b, tokens[i]);
stk.push(result);
}
}
return stk.top();
}
bool isOperand(const string &s) const
{
if (s == "+" || s == "-" || s == "*" || s == "/") return true;
return false;
}
int evaluate(int a, int b, string &op)
{
if (op == "+") return a+b;
if (op == "-") return a-b;
if (op == "*") return a*b;
return a/b;
}
};
//2014-2-19 update
int evalRPN(vector<string> &tokens)
{
stack<int> stk;
for (int i = 0; i < tokens.size(); i++)
{
if (isOperand(tokens[i]))
{
int b = stk.top(); stk.pop();
int a = stk.top(); stk.pop();
int t = evaluate(tokens[i], a, b);//a b 顺序不能搞错!且需要push入结果
stk.push(t);
}
else stk.push(stoi(tokens[i]));
}
return stk.top();
}
bool isOperand(string &c)
{
return c == "+" || c == "-" || c == "*" || c == "/";
}
int evaluate(string &op, int a, int b)
{
if (op == "+") return a+b;
if (op == "-") return a-b;
if (op == "*") return a*b;
return a/b;
}
分享到:
相关推荐
3 Evaluate Reverse Polish Notation 21 4 Isomorphic Strings 25 5 Word Ladder 27 6 Word Ladder II 29 7 Median of Two Sorted Arrays 33 8 Kth Largest Element in an Array 35 9 Wildcard Matching 37 10 ...
Leetcode的ac是什么意思 LeetCodeInJava List #98 Validate Binary Search Tree #100 Same Tree #104 Maximum Depth of Binary Tree #122 Best Time to Buy and Sell Stock II #136 Single Number #150 Evaluate ...
leetcode 不会评估反向波兰表示法 以逆波兰表示法计算算术表达式的值。 有效的运算符是 +、-、*、/。 每个操作数可以是整数或其他表达式。 笔记: 两个整数之间的除法应向零截断。 给定的 RPN 表达式始终有效。 这...
这是evaluate_reverse_polish_notation,这是evaluate_reverse_polish_notat
[Java](./src/Evaluate Reverse Polish Notation/Solution.java) 2013/11/27 中等的 [Java](./src/直线上的最大点数/Solution.java) 2013/11/22 难的 [Java](./src/排序列表/Solution.java) 2013/11/16 中等的 [Java...
Notation(150) Vector 向量 vector 是一种对象实体, 能够容纳许多其他类型相同的元素, 因此又被称为容器。 与string相同, vector 同属于STL(Standard Template Library, 标准模板库)中的一种自定义的数据类型, ...
Evaluate Reverse Polish Notation 逆波兰的后半截实现 Linked List Cycle 快慢指针 Linked List Cycle II 快慢指针再加个初始指针 慢指针到链表开始位置时, 快指针总是比他快k步(每次移动快1步, 移动k次), 第一次...
[leetcode]150.Evaluate Reverse Polish Notation 题目: ["2", "1", "+", "3", "*"] -> ((2 + 1) * 3) -> 9 ["4", "13", "5", "/", "+"] -> (4 + (13 / 5)) -> 6 思路:每次遇到符号,出栈两个元素进行运算,并将...
最大公共字符串leetcode leetcode刷题打卡 接下来,坚持每周至少刷一道LeetCode题,...Evaluate the value of an arithmetic expression in Reverse Polish Notation. Valid operators are+,-,*,/. Each operand may b
190 | [Reverse Bits](https://leetcode.com/problems/reverse-bits/) | [C++](./C++/reverse-bits.cpp) [Python](./Python/reverse-bits.py) | _O(1)_ | _O(1)_ | Easy ||| 191 |[Number of 1 Bits]...
LeetCodeLeetCode solutions(Java)树Minimum Depth of Binary Tree栈evaluate-reverse-polish-notation穷举max-points-on-a-line链表sort-list排序insertion-sort-list树binary-tree-postorder-traversal树binary-...
leetcode分发糖果 ...150-逆波兰表达式求值:evaluate-reverse-polish-notation 155-最小栈:min-stack Tree 普通二叉树 94-二叉树中序遍历:inorder-traversal 100-相同的二叉树:same-tree 101-对称二叉树:symmetric-
evaluate-reverse-polish-notation 链表 sort-list 排序 insertion-sort-list 树 binary-tree-postorder-traversal 树 binary-tree-preorder-traversal 链表 linked-list-cycle-ii 链表 linked-list-cycle 链表 copy...
Evaluate Reverse Polish Notation Implement Stack using Queues 队列 Implement Queue using Stacks 二叉树 二叉树的遍历 Binary Tree Preorder Traversal Binary Tree Inorder Traversal Binary Tree Postorder ...
链接:https://leetcode-cn.com/problems/evaluate-reverse-polish-notation/ 思路 运用lambda表达式和字典对运算符进行重载,再通过栈 stacks 对运算对象及中间结果进行存储 Python代码 class Solution: def ...