个人中心
文章发布
退出
作者热门文章
- ubuntu12.04环境下使用kvm ioctl接口实现最简单的虚拟机
- Ubuntu 通过无线网络安装Ubuntu Server启动系统后连接无线网络的方法
- 在Ubuntu上搭建网桥的方法
- ubuntu 虚拟机上网方式及相关配置详解
27
4
CFSDN坚持开源创造价值，我们致力于搭建一个资源共享平台，让每一个IT人在这里找到属于你的精彩世界.
这篇CFSDN的博客文章C++实现LeetCode(150.计算逆波兰表达式)由作者收集整理，如果你对这篇文章有兴趣，记得点赞哟.
Evaluate the value of an arithmetic expression in Reverse Polish Notation. 。
Valid operators are +, -, *, /. Each operand may be an integer or another expression. 。
Note
Example 1
Input: ["2", "1", "+", "3", "*"] Output: 9 Explanation: ((2 + 1) * 3) = 9 。
Example 2
Input: ["4", "13", "5", "/", "+"] Output: 6 Explanation: (4 + (13 / 5)) = 6 。
Example 3
Input: ["10", "6", "9", "3", "+", "-11", "*", "/", "*", "17", "+", "5", "+"] Output: 22 Explanation: ((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 。
逆波兰表达式就是把操作数放前面，把操作符后置的一种写法，我们通过观察可以发现，第一个出现的运算符，其前面必有两个数字，当这个运算符和之前两个数字完成运算后从原数组中删去，把得到一个新的数字插入到原来的位置，继续做相同运算，直至整个数组变为一个数字。于是按这种思路写了代码如下，但是拿到OJ上测试，发现会有Time Limit Exceeded的错误，无奈只好上网搜答案，发现大家都是用栈做的。仔细想想，这道题果然应该是栈的完美应用啊，从前往后遍历数组，遇到数字则压入栈中，遇到符号，则把栈顶的两个数字拿出来运算，把结果再压入栈中，直到遍历完整个数组，栈顶数字即为最终答案。代码如下
解法一:
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
class
Solution {
public
:
int
evalRPN(vector<string>& tokens) {
if
(tokens.size() == 1)
return
stoi(tokens[0]);
stack<
int
> st;
for
(
int
i = 0; i < tokens.size(); ++i) {
if
(tokens[i] !=
"+"
&& tokens[i] !=
"-"
&& tokens[i] !=
"*"
&& tokens[i] !=
"/"
) {
st.push(stoi(tokens[i]));
}
else
{
int
num1 = st.top(); st.pop();
int
num2 = st.top(); st.pop();
if
(tokens[i] ==
"+"
) st.push(num2 + num1);
if
(tokens[i] ==
"-"
) st.push(num2 - num1);
if
(tokens[i] ==
"*"
) st.push(num2 * num1);
if
(tokens[i] ==
"/"
) st.push(num2 / num1);
}
}
return
st.top();
}
};
|
我们也可以用递归来做，由于一个有效的逆波兰表达式的末尾必定是操作符，所以我们可以从末尾开始处理，如果遇到操作符，向前两个位置调用递归函数，找出前面两个数字，然后进行操作将结果返回，如果遇到的是数字直接返回即可，参见代码如下:
解法二:
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
class
Solution {
public
:
int
evalRPN(vector<string>& tokens) {
int
op = (
int
)tokens.size() - 1;
return
helper(tokens, op);
}
int
helper(vector<string>& tokens,
int
& op) {
string str = tokens[op];
if
(str !=
"+"
&& str !=
"-"
&& str !=
"*"
&& str !=
"/"
)
return
stoi(str);
int
num1 = helper(tokens, --op);
int
num2 = helper(tokens, --op);
if
(str ==
"+"
)
return
num2 + num1;
if
(str ==
"-"
)
return
num2 - num1;
if
(str ==
"*"
)
return
num2 * num1;
return
num2 / num1;
}
};
|
类似题目:
Basic Calculator 。
Expression Add Operators 。
参考资料:
https://leetcode.com/problemset/algorithms/ 。
https://leetcode.com/problems/evaluate-reverse-polish-notation/discuss/47642/a-recursive-solution-in-cpp 。
https://leetcode.com/problems/evaluate-reverse-polish-notation/discuss/47544/Challenge-me-neat-C%2B%2B-solution-could-be-simpler 。
到此这篇关于C++实现LeetCode(150.计算逆波兰表达式)的文章就介绍到这了,更多相关C++实现计算逆波兰表达式内容请搜索我以前的文章或继续浏览下面的相关文章希望大家以后多多支持我！ 。
原文链接：https://www.cnblogs.com/grandyang/p/4247718.html 。
最后此篇关于C++实现LeetCode(150.计算逆波兰表达式)的文章就讲到这里了,如果你想了解更多关于C++实现LeetCode(150.计算逆波兰表达式)的内容请搜索CFSDN的文章或继续浏览相关文章，希望大家以后支持我的博客！ 。
27
4
0
我正在解决以下leetcode问题：。。递归解是平凡的，所以我试着想出迭代解。下面是我的解决方案：。问题是：代码相对冗长，难以阅读。我的想法是跟踪从顶部到当前节点的整个路径。但这与标准DFS不同，因为
我正在解决以下leetcode问题：。。递归的解决方案是微不足道的，所以我试图拿出迭代的解决方案。下面是我的解决方案：。问题是：代码相对冗长，难以阅读。我的想法是跟踪从顶部到当前节点的整个路径。但这与
我正在处理 'Two Sum' problem in Leetcode . 我确信这段代码是正确的，我已经在 Repl 中对其进行了测试，它看起来是正确的，但 Leetcode 给了我一个错误。 这是
我正在研究 leetcode“762. 二进制表示中设置位的质数”，并且我测试了我的代码在 Jupiter Notebook 上运行良好，当我迁移到 leetcode 时，它显示 null 作为最
题干 请写出一个高效的在m*n矩阵中判断目标值是否存在的算法，矩阵具有如下特征： 每一行的数字都从左到右排序 每一行的第一个数字都比上一行最后一个数字大 用例 例如对于下面矩阵： [ [1,
LeetCode Monotone Stack Summary 单调栈小结 所谓的单调栈 Monotone Stack，就是栈内元素都是单调递增或者单调递减的，有时候需要严格的单调递增或递减，根据
第一题: 合并二叉树 LeetCode 617 : 合并二叉树 描述: 给定两个二叉树，想象当你将它们中的一个覆盖到另一个上时，两个二叉树的一些节点便会重叠。 你需要将他们合并为一个新的二叉树。合并的
和为k的子数组 LeetCode 560 和为k的不重复子数组个数(包含不连续)： 和为k的子数组 LeetCode 560 Example 1: Input:nums=[1,1,1],k=2 Ou
1.题目描述： 难度：简单 描述： 罗马数字包含以下七种字符: I， V， X， L，C，D 和 M。 字符 数值 I 1 V 5 X
1.题目描述： 难度：简单 描述： 给你一个整数 x ，如果 x 是一个回文整数，返回 true ；否则，返回 false 。 回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。 例如，1
一、题目描述 难道：简单 描述： 给你一个 升序排列 的数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。 由于在
一、题目描述 难度：简单 描述： 编写一个函数来查找字符串数组中的最长公共前缀。 如果不存在公共前缀，返回空字符串 “”。 示例 1： 输入：strs = ["flower","flow","flig
一、题目描述 难度：简单 描述： 将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 示例 1： 输入：l1 = [1,2,4], l2 = [1,3,4
@TOC 题目描述 给定一个只包括 ‘(’，‘)’，‘{’，‘}’，‘[’，‘]’ 的字符串 s ，判断字符串是否有效。 有效字符串需满足： 左括号必须用相同类型的右括号闭合。 左括号必须以正确的顺序
我已经在 Repl.it 网站上解决了这个问题，但是当我在 LeetCode 上提交代码时，它给出了一个 typeError，我将把它粘贴在这里: Line 29 in solution.js
var merge = function(nums1, m, nums2, n) { //contcating two array let array = nums2.concat(
我正在做以下leetCode问题:https://leetcode.com/problems/add-two-numbers/ 我不确定为什么我的一个测试用例失败了 所以问题是 You are giv
我正在尝试完成 Leetcode 上的 189. 旋转数组问题。这是我写的代码: class Solution(object): def rotate(self, nums, k):
该函数将反向打印链表的节点: void recur(ListNode head) { if(head == null) return; recur(head.next); tm
我正在尝试完成 Leetcode 上的 189. 旋转数组问题。这是我写的代码: class Solution(object): def rotate(self, nums, k):
我是一名优秀的程序员,十分优秀！