LeetCode·150.逆波兰表达式求值·栈模拟
2023-09-27 14:26:29 时间
作者:xun-ge-v
链接:https://leetcode.cn/problems/evaluate-reverse-polish-notation/solution/by-xun-ge-v-3w48/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
题目
示例
思路
解题思路
根据题意进行模拟:
- 去掉括号后表达式无歧义,上式即便写成 1 2 + 3 4 + * 也可以依据次序计算出正确结果。
- 适合用栈操作运算:遇到数字则入栈;遇到算符则取出栈顶两个数字进行计算,并将结果压入栈中
并且题目也给定了模拟的思路,根据这个思路模拟即可
具体实现:
我们定义一个栈,遇到数字则入栈;遇到算符则取出栈顶两个数字进行计算,并将结果压入栈中,最后返回栈定元素即可
代码
bool isNumber(char* token) {//判断当前字符串是符号还是数字
return strlen(token) > 1 || ('0' <= token[0] && token[0] <= '9');//当字符串长度大于2时,肯定就不是符号,当长度为1判断是不是0-9
}
int evalRPN(char** tokens, int tokensSize) {
int n = tokensSize;
int stk[n], top = -1;//初始化变量
for (int i = 0; i < n; i++) {//遍历字符串
char* token = tokens[i];
if (isNumber(token)) {//判断是否为数字
stk[++top] = atoi(token);//数字入数字栈
} else {//遇到算符则取出栈顶两个数字进行计算,并将结果压入栈中
int num2 = stk[top];
int num1 = stk[--top];
switch (token[0]) {
case '+':
stk[top] = num1 + num2;
break;
case '-':
stk[top] = num1 - num2;
break;
case '*':
stk[top] = num1 * num2;
break;
case '/':
stk[top] = num1 / num2;
break;
}
}
}
return stk[top];
}
作者:xun-ge-v
链接:https://leetcode.cn/problems/evaluate-reverse-polish-notation/solution/by-xun-ge-v-3w48/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
相关文章
- 【LeetCode】跳跃游戏 [M](模拟)
- 【LeetCode】最大的以 1 为边界的正方形 [M](模拟)
- 【LeetCode】统计全 1 子矩形(单调栈)
- LeetCode_字符串_简单_415.字符串相加
- LeetCode_二分搜索_困难_154.寻找旋转排序数组中的最小值 II
- LeetCode_模拟_中等_799.香槟塔
- LeetCode_动态规划_中等_198.打家劫舍
- LeetCode·每日一题·2437. 有效时间的数目·模拟
- LeetCode·1669.合并两个链表·双指针
- LeetCode·每日一题·1945.字符串转化后的各位数组之和·模拟
- LeetCode·每日一题·1106.解析布尔表达式·栈模拟
- LeetCode·每日一题·915.分割数组·模拟
- LeetCode·每日一题·1768.交替合并字符串·模拟
- LeetCode·每日一题·817.链表组件·模拟+哈希
- LeetCode·每日一题·1790.仅执行一次字符串交换能否使两个字符串相等·模拟
- LeetCode·516.最长回文子序列·动态规划
- LeetCode·每日一题·面试题 01.09.字符串轮转·模拟
- LeetCode·71.简化路径·栈模拟
- LeetCode·455.分发饼干·贪心
- LeetCode·每日一题·1582.二进制矩阵中的特殊位置·模拟
- 【LeetCode从零单排】No15 3Sum
- leetcode 春季编程大赛-个人赛
- [LeetCode] 323. Number of Connected Components in an Undirected Graph 无向图中的连通区域的个数
- leetcode 62 不同路径