请写一个整数计算器，支持加减乘三种运算和括号。
数据范围：
，保证计算结果始终在整型范围内
要求：空间复杂度： )
，时间复杂度
[编程题]表达式求值
面向debug编程了属于是
class Solution:
def solve(self , s: str) -> int:
# write code here
return self.solve1(s)[0]
def solve1(self, s: str,flag=False,minor=False) :
# write code here
i = 0
res = 0
left = 0
stack1 = []
last = 0
while i < len(s):
# print(s[i],i,res)
# time.sleep(0.1)
while s[i] == '('&nbs***bsp;stack1:
if s[i]=='(':
if not stack1:
left = i + 1
stack1.append('(')
if s[i] == ')':
stack1.pop()
if not stack1:
res,off = self.solve1(s[left:i]) # result
i=left+off+1
break
i += 1
if i>=len(s):
break
if s[i] == '*':
temp,off = self.solve1(s[i + 1:],True)
res = res * temp
elif s[i] == '+':
temp, off = self.solve1(s[i + 1:])
res = res + temp
elif s[i] == '-':
temp, off = self.solve1(s[i + 1:],minor=True)
res = res - temp
else:
res, off = self.find_digit(s[i:])
i= i+off+1
if flag:
return res,i
elif minor:
if i<len(s) and s[i]!='*':
return res,i
return res,i
def find_digit(self, s):
res = ''
i = 0
for i, v in enumerate(s):
if v >= '0' and v <= '9':
res += v
else:
return int(res) if res else 0, i-1
break
return int(res) if res else 0, i
发表于 2023-04-03 22:26:32
回复(0)
class Solution:
def solve(self , s: str) -> int:
# write code here
return eval(s)
发表于 2023-03-18 17:02:43
回复(2)
以"2*(3-3-2*3) "为例，
问题可拆解为：
① 计算所有括号内表达式 [递归] ，初始表达式可在左右两侧加括号，视为"( 2*(3-3-2*3) )"；
② 计算多个值累加，每个表达式可视为多元素累加 [列表储存]。元素包括：乘积结果，eg. 2*3 视为 +(2*3)；被减数的相反数，eg. -3记为+(-3）；加数与被加数。即在列表内存储 [3, -3, -6=(-2)*3]，累加；
③ 计算乘法；
④ 获取数字，eg. '11'。
具体方法：表达式s从前至后依次处理，当s长度为0时，程序结束。为方便理解，由④至①倒序说明。
④ 获取数字
s=‘（11*(3-1) )’，获取11，更新后字符串为s='*(3-1)';
③ 乘法
s=‘（11*(3-1) )’
将数字11入栈，判断更新后字符串第一个元素为“*”，栈顶11出栈并与括号内运算结果（）相乘，相乘结果入栈；
② 累加
每个括号对应一个栈，栈内保存的确定元素一定是取反后、乘积、子括号内表达式的值，确定元素指除了栈顶的其余元素（栈顶可能参与后续运算：乘法）。
新调用递归函数，第一个字符为数值，提取数字后入栈；
接下来运算符为“-”，提取后面数字或括号表达式的值，取相反数后入栈；
运算符为“*”，提取后面数字或括号表达式的值，将栈顶出栈并与之相乘，乘积入栈；
接下来运算符为“+”，提取后面数字或括号表达式的值，入栈。
① 识别到 “(”【记为'(1'】，说明遇到新的括号，调用递归函数，将该 "(" 后的字符串【记为‘s1’】传入；识别到数字，根据②计算；后续根据②③④提到的场景计算。
遇到 ')'，最内层子括号结束计算，返回最内层子括号表达式的值，并将该值入栈（倒数第二层子括号表达式对应的栈）；依次迭代，直到最外层括号（初始表达式）计算完成。
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 返回表达式的值
# @param s string字符串 待计算的表达式
# @return int整型
class Solution:
def solve(self , s: str) -> int:
class Stack(object):
def __init__(self) -> None:
self.item = []
def push(self, node):
self.item.append(node)
def pop(self):
return self.item.pop()
def top(self):
return self.item[-1]
def isEmpty(self):
if self.item == []:
return True
else:
return False
def get_num(item, s) -> tuple():
li = [int(item)]
while s:
if s[0].isdigit():
li.append(int(s[0]))
s = s[1:]
else:
break
num = 0
for i in range(len(li)):
num += li[i] * 10 ** (len(li)-i-1)
return num, s
def cal_bracket(s) -> tuple():
stack_str = Stack()
stack_num = Stack()
while s:
item, s = s[0], s[1:]
if item == '(':
num, s = cal_bracket(s)
stack_num.push(num)
elif item == ')':
return (sum(stack_num.item), s) # 本cal_bracket结束，返回: ()计算值，新的s
elif item == '*':
if s[0] == '(':
num, s = cal_bracket(s[1:])
stack_num.push(stack_num.pop() * num)
elif s[0].isdigit():
num, s = get_num(s[0], s[1:])
stack_num.push(stack_num.pop() * num)
elif item == '+':
pass
elif item == '-':
if s[0] == '(':
num, s = cal_bracket(s[1:])
stack_num.push(-num)
elif s[0].isdigit():
num, s = get_num(s[0], s[1:])
stack_num.push(-num)
elif item.isdigit():
num, s = get_num(item, s)
stack_num.push(num)
s = s + ')'
return cal_bracket(s)[0]
发表于 2022-10-19 22:01:02
回复(0)
写的很拉，勉勉强强
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 返回表达式的值
# @param s string字符串 待计算的表达式
# @return int整型
#
#中缀表达式问题
class Solution:
def solve(self , s: str) -> int:
# 定义优先级
level = {
'*': 2,
'-': 1,
'+': 1,
'(': 3,
')': -1
}
num = []
signal = []
# write code here
signal.append('(')
s = s + ')'
l = len(s)
i = 0
while i < l:
t = i
while(s[t].isdigit()):
t = t + 1
if(t != i):
num.append(int(s[i:t]))
i = t
continue
if(signal[-1] == '(' and s[i] != ')'):
signal.append(s[i])
i = i + 1
elif (level[s[i]] > level[signal[-1]]):
signal.append(s[i])
i = i + 1
elif (level[s[i]] <= level[signal[-1]]):
if (s[i] == ')' and signal[-1] == '('):
signal.pop()
i = i + 1
else:
a = num.pop()
b = num.pop()
num.append(eval("{} {} {}".format(b, signal[-1], a)))
signal.pop()
return num[-1]
发表于 2022-09-12 16:19:06
回复(0)
C++
class Solution {
public:
int cct(stack<int> &number, stack<char> &operation)
{
int tmp_1 = number.top();
number.pop();
int tmp_2 = number.top();
number.pop();
char tmp_o = operation.top();
operation.pop();
if (tmp_o == '+')
return tmp_2 + tmp_1;
else if (tmp_o == '-')
return tmp_2 - tmp_1;
else
return tmp_1 * tmp_2;
}
int solve(string s) {
stack<int> nmb;
stack<char> opt;
for (int i = 0; i < s.size(); i++)
{
for (int j = 0, i_ofs = 0;; i_ofs++)
if (s[i + i_ofs] > 47) // 该字符是数字。
j = j * 10 + s[i + i_ofs] - 48;
else // 该字符是运算符。
{
if (i_ofs)
nmb.push(j);
i += i_ofs;
break;
}
if (i >= s.size())
break;
while (s[i] % 2 && !opt.empty() && opt.top() != '(') // s[i] == ')', '+', '-';
nmb.push(cct(nmb, opt));
s[i] == ')' ? opt.pop() : opt.push(s[i]);
}
while (!opt.empty())
nmb.push(cct(nmb, opt));
return nmb.top();
}
}; Python
class Solution: def solve(self , s: str) -> int: return eval(s)
发表于 2022-08-12 15:23:59
回复(0)
import re, json
a = "(2*(13-4))*5"
# a = "1+2"
# a = "-3-2*3*4-1"
# a = a.strip()
# a = a.replace(" ","")
# a = re.split("([\*\-\+\(\)])", a)
# c = ["(", ")", "+", "-", "*"]
# d = [x for x in a if x]
# print(a)
# print(d)
class Solution:
def solve(self, s: str) -> int:
# write code here
s = s.strip()
index = 0
res = 0
num = 0
stack = []
sign = "+"
while index < len(s):
if s[index] == " ":
index += 1
continue
if s[index] == "(":
end = index + 1
lens = 1
while lens > 0:
if s[end] == "(":
lens += 1
if s[end] == ")":
lens -= 1
end += 1
num = self.solve(s[index+1 : end-1])
index = end - 1
continue
if '0' <= s[index] <= '9':
num = num * 10 + int(s[index])
if not '0' <= s[index] <= '9' or index == len(s) - 1:
if sign == "+":
stack.append(num)
elif sign == "-":
stack.append(-1 * num)
elif sign == "*":
stack.append(stack.pop() * num)
num = 0
sign = s[index]
index += 1
while stack:
res += stack.pop()
return res
s = Solution()
print(s.solve(a))
a = "(2*(13-4))*5"
# a = "1+2"
# a = "-3-2*3*4-1"
# a = a.strip()
# a = a.replace(" ","")
# a = re.split("([\*\-\+\(\)])", a)
# c = ["(", ")", "+", "-", "*"]
# d = [x for x in a if x]
# print(a)
# print(d)
class Solution:
def solve(self, s: str) -> int:
# write code here
s = s.strip()
index = 0
res = 0
num = 0
stack = []
sign = "+"
while index < len(s):
if s[index] == " ":
index += 1
continue
if s[index] == "(":
end = index + 1
lens = 1
while lens > 0:
if s[end] == "(":
lens += 1
if s[end] == ")":
lens -= 1
end += 1
num = self.solve(s[index+1 : end-1])
index = end - 1
continue
if '0' <= s[index] <= '9':
num = num * 10 + int(s[index])
if not '0' <= s[index] <= '9' or index == len(s) - 1:
if sign == "+":
stack.append(num)
elif sign == "-":
stack.append(-1 * num)
elif sign == "*":
stack.append(stack.pop() * num)
num = 0
sign = s[index]
index += 1
while stack:
res += stack.pop()
return res
s = Solution()
print(s.solve(a))
发表于 2022-08-11 18:08:20
回复(0)
class Solution:
def solve(self , s ):
# write code here
self.op_priority = {'+': 0, '-': 0, '*': 1}
suffix_expression = self.infix2suffix(s)
return self.suffix2result(suffix_expression)
def suffix2result(self, suffix_expression):
stack = []
for op in suffix_expression:
if op not in ['+', '-', '*']:
stack.append(int(op))
else:
num1 = stack.pop()
num2 = stack.pop()
if op == '+':
temp = num2 + num1
elif op == '-':
temp = num2 - num1
else:
temp = num2 * num1
stack.append(temp)
return stack.pop()
def infix2suffix(self, s):
sop, L, i = [], [], 0
while i < len(s):
if self.isNum(s[i]):
num = ''
while i < len(s) and self.isNum(s[i]):
num += s[i]
i += 1
L.append(num)
elif s[i] == '(':
sop.append(s[i])
i += 1
elif s[i] == ')':
while sop[-1] != '(':
L.append(sop.pop())
sop.pop()
i += 1
else:
while True:
if sop == []&nbs***bsp;sop[-1] == '('&nbs***bsp;(self.op_priority[s[i]] > self.op_priority[sop[-1]]):
sop.append(s[i])
break
else:
L.append(sop.pop())
i += 1
while sop:
L.append(sop.pop())
return L
def isNum(self, ch):
if ch in ['0', '1', '2', '3', '4', '5', '6', '7', '8', '9']:
return True
else:
return False
发表于 2021-09-23 00:39:17
回复(0)
问题信息
难度：
9条回答
1959收藏
6392浏览
通过挑战的用户
查看代码-
2022-09-16 16:05:14
-
2022-09-16 15:14:19
-
2022-09-16 15:06:25
-
2022-09-16 13:45:22 -
2022-09-16 11:57:24
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K2座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
