利用栈/递归求解算术表达式 LeetCode 224. Basic Calculator

2024-03-17 15:58
文章标签 leetcode 表达式 递归 求解 basic 算术 calculator 224

本文主要是介绍利用栈/递归求解算术表达式 LeetCode 224. Basic Calculator，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

概括一句话就是： 遇到)或者优先级比即将读入元素低的符号，都要把栈弹出到不能再次弹出为止

符号和运算符可以分为两个栈


 运算符的优先级
 

优先级运算符
1括号()
2负号-
3乘方**
4乘*，除/，求余%
5加+，减-
6小于<，小于等于<=，大于>，大于等于>=
7等于==，不等于!=
8逻辑与&&
9逻辑或||


大致的规律是，一元运算符 > 二元运算符 > 多元运算符。

利用堆栈解析算术表达式的过程

中缀表达式翻译成后缀表达式的方法如下：

（1）从左向右依次取得数据ch。

（2）如果ch是操作数，直接输出。

（3）如果ch是运算符（含左右括号），则：
      a：如果ch = '('，放入堆栈。
      b：如果ch = ')'，依次输出堆栈中的运算符，直到遇到'('为止。
      c：如果ch不是')'或者'('，那么就和堆栈顶点位置的运算符top做优先级比较。
          1：如果ch优先级比top高，那么将ch放入堆栈。
          2：如果ch优先级低于或者等于top，那么输出top，然后将ch放入堆栈。

（4）如果表达式已经读取完成，而堆栈中还有运算符时，依次由顶端输出。

如果我们有表达式(A-B)*C+D-E/F，要翻译成后缀表达式，并且把后缀表达式存储在一个名叫output的字符串中，可以用下面的步骤。

（1）读取'('，压入堆栈，output为空
（2）读取A，是运算数，直接输出到output字符串，output = A
（3）读取'-'，此时栈里面只有一个'('，因此将'-'压入栈，output = A
（4）读取B，是运算数，直接输出到output字符串，output = AB
（5）读取')'，这时候依次输出栈里面的运算符'-'，然后就是'('，直接弹出，output = AB-
（6）读取'*'，是运算符，由于此时栈为空，因此直接压入栈，output = AB-
（7）读取C，是运算数，直接输出到output字符串，output = AB-C
（8）读取'+'，是运算符，它的优先级比'*'低，那么弹出'*'，压入'+"，output = AB-C*
（9）读取D，是运算数，直接输出到output字符串，output = AB-C*D
（10）读取'-'，是运算符，和'+'的优先级一样，因此弹出'+'，然后压入'-'，output = AB-C*D+
（11）读取E，是运算数，直接输出到output字符串，output = AB-C*D+E
（12）读取'/'，是运算符，比'-'的优先级高，因此压入栈，output = AB-C*D+E
（13）读取F，是运算数，直接输出到output字符串，output = AB-C*D+EF
（14）原始字符串已经读取完毕，将栈里面剩余的运算符依次弹出，output = AB-C*D+EF/-

5 计算算术表达式

当有了后缀表达式以后，运算表达式的值就非常容易了。可以按照下面的流程来计算。

（1）从左向右扫描表达式，一个取出一个数据data
（2）如果data是操作数，就压入堆栈
（3）如果data是操作符，就从堆栈中弹出此操作符需要用到的数据的个数，进行运算，然后把结果压入堆栈
（4）如果数据处理完毕，堆栈中最后剩余的数据就是最终结果。

比如我们要处理一个后缀表达式1234+*+65/-，那么具体的步骤如下。

（1）首先1，2，3，4都是操作数，将它们都压入堆栈
（2）取得'+'，为运算符，弹出数据3，4，得到结果7，然后将7压入堆栈
（3）取得'*'，为运算符，弹出数据7，2，得到数据14，然后将14压入堆栈
（4）取得'+'，为运算符，弹出数据14，1，得到结果15，然后将15压入堆栈
（5）6，5都是数据，都压入堆栈
（6）取得'/'，为运算符，弹出数据6，5，得到结果1.2，然后将1.2压入堆栈

 

（7）取得'-'，为运算符，弹出数据15，1.2，得到数据13.8，这就是最后的运算结果.

 

某些奇葩情况下会让写递归的：

这个时候比较好的思路是找最右边的优先级最低的运算符，这样整个串就被划分成两部分：

#include <stdio.h>
#include <string>
#include <vector>
#include <algorithm>
#include <map>
#include <set>
#include <iostream>
#include <memory.h>
using namespace std;
inline int calTwo(char ch,int a, int b) {if (ch == '+')return a+b;else if (ch == '-')return a-b;else if (ch == '*')return a*b;elsereturn a/b;
}
inline int getOp(char ch) {if (ch == '+' || ch == '-')return 0;else if (ch == '*' || ch == '/')return 1;else return 2;
}
int cal(const string& str, int s, int e){if (str[s] == '(' && str[e] == ')')return cal(str, s + 1, e - 1);if (s == e)return str[s] - '0';int leftBracket = 0, minPos = s, minOp = 1;for (int i = s; i <= e; ++i) {if (leftBracket == 0 && getOp(str[i]) <= minOp) {minPos = i;minOp = getOp(str[i]);}else if (str[i] == '(')++leftBracket;else if (str[i] == ')')--leftBracket;}int left = cal(str, s, minPos - 1);int right = cal(str, minPos + 1, e);int res = calTwo(str[minPos],left,right);return res;
}int main()
{string str = "2+1-6*3/(1+1)";int res = cal(str, 0, str.length() - 1);return 0;
};

 

非递归的简洁写法：

#include <iostream>
#include <string>
#include <stack>
using namespace std;
int getPri(char ch) {if (ch == '(')return 0;if (ch == '+' || ch == '-')return 1;else if (ch == '*' || ch == '/')return 2;elsereturn 3;
}
int operate(char ch, int x, int y) {if (ch == '+')return x + y;else if (ch == '-')return x - y;else if (ch == '*')return x * y;elsereturn x/y;
}
void parse(stack<char>& op, stack<int>& num) {int x = num.top();num.pop();int y = num.top();num.pop();int z = operate(op.top(), x, y);op.pop();num.push(z);
}int cal(const string& str) {stack<int> num;stack<char> op;int len = str.length(), i, j;for (i = 0; i < len; ++i) {if (str[i] >= '0' && str[i] <= '9')num.push(str[i]-'0');else {if (str[i] == '(') op.push(str[i]);else if (str[i] == ')') {while (op.top() != '(') parse(op, num);op.pop();}else if (op.empty() || getPri(str[i]) > getPri(op.top()))op.push(str[i]);else {while (!op.empty() || getPri(str[i]) <= getPri(op.top())) parse(op,num);op.push(str[i]);}}}while (!op.empty()) parse(op,num);return num.top();
}
int main()
{//string  str = "(1+2)*3-4";//string  str = "1+2*3";//string  str = "(1+2)*3/2";string str = "2*(1+2*5)";cout<<cal(str)<<endl;return 0;
}

Python Version:

class Solution:def FetchNum(self, str, pos, len):res = 0while (pos < len and str[pos] >= '0' and str[pos] < '9'):res = res*10 + (int(str[pos]))pos += 1return res, pos-1def CalValue(self, a, b, op):if (op == '+'):return a+belif (op == '-'):return a-belif (op == '*'):return a*belif (op == '/'):return a/bdef CalTop(self, nums, ops):b = nums.pop()a = nums.pop()op = ops.pop()c = self.CalValue(a, b, op)return cdef CalMathVal(self, str):slen = len(str)i = 0priDict = {'+':1, '-':1, '*':2, '/':2, '(':0}nums, ops = [], []while (i < slen):if (str[i] >= '0' and str[i] < '9'):num, i = self.FetchNum(str, i, slen)nums.append(num)elif (str[i] in priDict and ((ops and priDict[str[i]] > priDict[ops[-1]]) or (not ops))):ops.append(str[i])elif (str[i] == '('):ops.append(str[i])elif (str[i] in priDict and ((ops and priDict[str[i]] <= priDict[ops[-1]]) or (not ops)) ):c = self.CalTop(nums, ops)nums.append(c)ops.append(str[i])elif (str[i] == ')'):if(ops):c = self.CalTop(nums, ops)if (ops[-1] == '('):ops.pop()nums.append(c)i += 1while (ops):c = self.CalTop(nums, ops)nums.append(c)return nums[-1]s = Solution()
y = s.CalMathVal("(2+3)*(1+4)")
print(y)

后记：

上述解法并没有考虑单目运算符的情况，如果是单目运算符，只可能是开头-x或者括号内(-x)，多一种FetchNum的情况即可。

 

最后来一道LeetCode题目：

Implement a basic calculator to evaluate a simple expression string.

The expression string may contain open ( and closing parentheses ), the plus + or minus sign -, non-negative integers and empty spaces .

Example 1:

Input: "1 + 1"
Output: 2

Example 2:

Input: " 2-1 + 2 "
Output: 3

Example 3:

Input: "(1+(4+5+2)-3)+(6+8)"
Output: 23

Note:

  • You may assume that the given expression is always valid.
  • Do not use the eval built-in library function.

--------------------------------------------

from typing import Listclass Solution:def calculate(self, s: str) -> int:def fetch_num(s1, pos):res = 0while (pos < len(s1) and s1[pos] >= '0' and s1[pos] <= '9'):res = res * 10 + ord(s1[pos])-ord('0')pos += 1return res,posdef cal_top(n1, o1):if (len(n1) >= 2 and len(o1) >= 1):b = n1.pop()a = n1.pop()op = o1.pop()res = a + b if op == '+' else a - bn1.append(res)l, i = len(s), 0nums, ops = [], []while (i < l):print("nums={0} ops={1}".format(nums,ops))if (s[i] >= '0' and s[i] <= '9'):num, i = fetch_num(s, i)nums.append(num)elif (s[i] == '('):ops.append('(')i += 1elif (s[i] in {'+', '-'}):if (ops and ops[-1] in {'+', '-'}):cal_top(nums, ops)ops.append(s[i])i += 1elif (s[i] == ')'):if (ops and ops[-1] == '('): #bug1ops.pop()else:cal_top(nums, ops)if (ops and ops[-1] == '('): #bug2ops.pop()i += 1else:i += 1cal_top(nums, ops)return nums[-1]s = Solution()
#print(s.calculate("(7)-(0)+(4)"))
print(s.calculate("(1+(4+5+2)-3)+(6+8)"))

 

这篇关于利用栈/递归求解算术表达式 LeetCode 224. Basic Calculator的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/819422。

相关文章

Spring Security 基于表达式的权限控制

Spring Security 基于表达式的权限控制

前言 spring security 3.0已经可以使用spring el表达式来控制授权，允许在表达式中使用复杂的布尔逻辑来控制访问的权限。 常见的表达式 Spring Security可用表达式对象的基类是SecurityExpressionRoot。 表达式描述hasRole([role])用户拥有制定的角色时返回true （Spring security默认会带有ROLE_前缀）,去
阅读更多...
哈希leetcode-1

哈希leetcode-1

目录 1前言 2.例题  2.1两数之和 2.2判断是否互为字符重排 2.3存在重复元素1 2.4存在重复元素2 2.5字母异位词分组 1前言 哈希表主要是适合于快速查找某个元素（O(1)） 当我们要频繁的查找某个元素，第一哈希表O(1)，第二，二分O(log n) 一般可以分为语言自带的容器哈希和用数组模拟的简易哈希。 最简单的比如数组模拟字符存储，只要开26个c
阅读更多...
C++11第三弹：lambda表达式 | 新的类功能 | 模板的可变参数

C++11第三弹：lambda表达式 | 新的类功能 | 模板的可变参数

🌈个人主页： 南桥几晴秋 🌈C++专栏： 南桥谈C++ 🌈C语言专栏： C语言学习系列 🌈Linux学习专栏： 南桥谈Linux 🌈数据结构学习专栏： 数据结构杂谈 🌈数据库学习专栏： 南桥谈MySQL 🌈Qt学习专栏： 南桥谈Qt 🌈菜鸡代码练习： 练习随想记录 🌈git学习： 南桥谈Git 🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈�
阅读更多...
06 C++Lambda表达式

06 C++Lambda表达式

lambda表达式的定义 没有显式模版形参的lambda表达式 [捕获] 前属性 (形参列表) 说明符 异常 后属性 尾随类型 约束 {函数体} 有显式模版形参的lambda表达式 [捕获] <模版形参> 模版约束 前属性 (形参列表) 说明符 异常 后属性 尾随类型 约束 {函数体} 含义 捕获：包含零个或者多个捕获符的逗号分隔列表 模板形参：用于泛型lambda提供个模板形参的名
阅读更多...
leetcode-24Swap Nodes in Pairs

leetcode-24Swap Nodes in Pairs

带头结点。 /*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode(int x) { val = x; }* }*/public class Solution {public ListNode swapPairs(L
阅读更多...
leetcode-23Merge k Sorted Lists

leetcode-23Merge k Sorted Lists

带头结点。 /*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode(int x) { val = x; }* }*/public class Solution {public ListNode mergeKLists
阅读更多...
C++ | Leetcode C++题解之第393题UTF-8编码验证

C++ | Leetcode C++题解之第393题UTF-8编码验证

题目： 题解： class Solution {public:static const int MASK1 = 1 << 7;static const int MASK2 = (1 << 7) + (1 << 6);bool isValid(int num) {return (num & MASK2) == MASK1;}int getBytes(int num) {if ((num &
阅读更多...
【每日一题】LeetCode 2181.合并零之间的节点（链表、模拟）

【每日一题】LeetCode 2181.合并零之间的节点（链表、模拟）

【每日一题】LeetCode 2181.合并零之间的节点（链表、模拟） 题目描述 给定一个链表，链表中的每个节点代表一个整数。链表中的整数由 0 分隔开，表示不同的区间。链表的开始和结束节点的值都为 0。任务是将每两个相邻的 0 之间的所有节点合并成一个节点，新节点的值为原区间内所有节点值的和。合并后，需要移除所有的 0，并返回修改后的链表头节点。 思路分析 初始化：创建一个虚拟头节点
阅读更多...
C语言 | Leetcode C语言题解之第393题UTF-8编码验证

C语言 | Leetcode C语言题解之第393题UTF-8编码验证

题目： 题解： static const int MASK1 = 1 << 7;static const int MASK2 = (1 << 7) + (1 << 6);bool isValid(int num) {return (num & MASK2) == MASK1;}int getBytes(int num) {if ((num & MASK1) == 0) {return
阅读更多...
【JavaScript】LeetCode：16-20

【JavaScript】LeetCode：16-20

文章目录 16 无重复字符的最长字串17 找到字符串中所有字母异位词18 和为K的子数组19 滑动窗口最大值20 最小覆盖字串 16 无重复字符的最长字串 滑动窗口 + 哈希表这里用哈希集合Set()实现。左指针i，右指针j，从头遍历数组，若j指针指向的元素不在set中，则加入该元素，否则更新结果res，删除集合中i指针指向的元素，进入下一轮循环。 /*** @param
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2