首页 > 试题广场 >

表达式求值

[编程题]表达式求值
  • 热度指数：107365 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
请写一个整数计算器，支持加减乘三种运算和括号。

数据范围：，保证计算结果始终在整型范围内

要求：空间复杂度： ，时间复杂度
示例1

输入

"1+2"

输出

3
示例2

输入

"(2*(3-4))*5"

输出

-10
示例3

输入

"3+2*3*4-1"

输出

26
算法知识视频讲解
添加回答
Python
牛客988600999号头像 牛客988600999号
class Solution:
    def solve(self , s ):
        return eval(s)
发表于 2021-08-04 11:10:50 回复(0)
Python
奋斗的习习张头像 奋斗的习习张 
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
# 返回表达式的值
# @param s string字符串 待计算的表达式
# @return int整型
#
# 最变态的题目了
class Solution:
    def solve(self , s ):
        # write code here
        while "(" in s:
            start = s.rfind("(")
            end = s[start:].find(")") + start
            sub_str = s[start: end + 1]
            temp = self.cal_no_brackets(sub_str[1:-1])
            #print temp, s, start
            if temp < 0:
                if s[start-1] == "+":
                    s = s.replace(sub_str, "0"+str(temp))
                elif s[start-1] == "-":
                    s = s.replace("-" + sub_str, "+" + str(-temp))
                else:
                    s = s.replace(sub_str, str(temp))

            else:
                s = s.replace(sub_str, str(temp))
        res = self.cal_no_brackets(s)
        return res

    def cal_no_brackets(self, string):
        array = self.split_string_to_array(string)
        if len(array) == 1:
            return int(array[0])
        while "*" in array:
            index = array.index("*")
            number1 = int(array[index-1])
            if array[index+1] == "-":
                number2 = -1*(int(array[index+2]))
                array = array[:index - 1] + [number1 * number2] + array[index + 3:]
            else:
                number2 = int(array[index + 1])
                array = array[:index-1] + [number1*number2] + array[index+2:]
        while len(array) != 1:
            if array[0] == "-" and len(array) == 2:
                return -array[1]
            elif array[1] == "+":
                array = [int(array[0]) + int(array[2])] + array[3:]
            else:
                array = [int(array[0]) - int(array[2])] + array[3:]
        return array[0]

    def split_string_to_array(self, string):
        array = []
        temp = ""
        for index in range(len(string)):
            if "0" <= string[index] <= "9":
                temp += string[index]
            else:
                if temp:
                    array.append(temp)
                temp = ""
                array.append(string[index])
        array.append(temp)
        return array

发表于 2021-07-18 17:50:56 回复(0)
Python
spongebob7头像 spongebob7
class Solution:
    def solve(self , s ):
        # write code here
        return eval(s)
发表于 2021-04-07 20:50:31 回复(6)
Python
自我定位头像 自我定位
思路：
看到该题时，分析出目标为“计算一个表达式的值”，首先想到了计算机的后缀表达式法，使用栈的特性求解后缀表达式。所以将该题分成了两个部分：
第一部分：
将输入的表达式字符串转换成后缀表达式
第二部分：
计算后缀表达式的值
def solve(s):
    # write code here
    # 第一部分：转换为后缀表达式
    dic = {    # 字典定义运算符的顺序
        "(": 0,
        "+": 1,
        "-": 1,
        "*": 2
    }
    stack = []
    expr = []
    tmpnum = "" 
    for x in s:
        if x in "0123456789":
            tmpnum += x
        else:
            if tmpnum != "":
                expr.append(tmpnum)
                tmpnum = ""
            if x == "(":
                stack.append(x)
            elif x == ")":
                tmp = stack[len(stack) - 1]
                while tmp != "(":
                    tmp = stack.pop()
                    expr.append(tmp)
                    tmp = stack[len(stack) - 1]
                stack.pop()
            else:
                while len(stack) > 0 and dic[stack[len(stack) - 1]] >= dic[x]:
                    expr.append(stack.pop())
                stack.append(x)
    if tmpnum != "":
        expr.append(tmpnum)
    if len(stack) > 0:
        stack.reverse()
        expr.extend(stack)
    stack = []
    # 第二部分：计算后缀表达式的值
    for x in expr:
        if x in "+-*":
            a = stack.pop()
            b = stack.pop()
            a = eval(str(b) + x + str(a))
            stack.append(a)
        else:
            stack.append(x)
    return stack[0]
发表于 2021-03-31 11:41:59 回复(0)
Python
蜘蛛θ..θ头像 蜘蛛θ..θ 
class Solution:
    def solve(self , s ):
        return eval(s)

发表于 2020-10-27 13:01:32 回复(3)
提交观点

问题信息

栈 递归
难度：
6条回答 11017浏览

热门推荐

通过挑战的用户

查看代码

相关试题

表达式求值

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号