欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

算法实践:表达式求值

程序员文章站 2022-03-24 15:24:18
...

表达式求值

描述

求一个可以带括号的小学算术四则运算表达式的值

输入

一行,一个四则运算表达式。’*‘表示乘法,’/'表示除法

输出

一行,该表达式的值,输出的结果为整数。

样例

输入样例1:
34
输入样例2:
7+8
输入样例3:
1611+1697-(2110-(2337-(649+(875+2933)-3536)))
输出样例1:
34
输出样例2:
15
输出样例3:
26142413
3142

难度

解法

偷懒方法,栈,递归

代码

偷懒方法

def Max(a,b):
    return max(a,b)
def Min(a,b):
    return min(a,b)


s = input()
print(eval(s))

def compare(op1, op2):
    return op1 in ["*", "/"] and op2 in ["+", "-"]


def getvalue(num1, num2, operator):
    if operator == "+":
        return num1 + num2
    elif operator == "-":
        return num1 - num2
    elif operator == "*":
        return num1 * num2
    else:  # /
        return num1 // num2


def process(data, opt):
    operator = opt.pop()
    num2 = data.pop()
    num1 = data.pop()
    data.append(getvalue(num1, num2, operator))


def calculate(s):
    data = []  # 数据栈
    opt = []  # 操作符栈
    i = 0  # 表达式遍历索引
    while i < len(s):
        if s[i].isdigit():  # 数字,入栈data
            start = i  # 数字字符开始位置
            while i + 1 < len(s) and s[i + 1].isdigit():
                i += 1
            data.append(int(s[start: i + 1]))  # i为最后一个数字字符的位置
        elif s[i] == ")":  # 右括号,opt出栈同时data出栈并计算,计算结果入栈data,直到opt出栈一个左括号
            while opt[-1] != "(":
                process(data, opt)
            opt.pop()  # 出栈"("
        elif not opt or opt[-1] == "(":  # 操作符栈为空,或者操作符栈顶为左括号,操作符直接入栈opt
            opt.append(s[i])
        elif s[i] == "(" or compare(s[i], opt[-1]):  # 当前操作符为左括号或者比栈顶操作符优先级高,操作符直接入栈opt
            opt.append(s[i])
        else:  # 优先级不比栈顶操作符高时,opt出栈同时data出栈并计算,计算结果如栈data
            while opt and not compare(s[i], opt[-1]):
                if opt[-1] == "(":  # 若遇到左括号,停止计算
                    break
                process(data, opt)
            opt.append(s[i])
        i += 1  # 遍历索引后移
    while opt:
        process(data, opt)
    print(data.pop())


if __name__ == '__main__':
    #exp = "(9+((3-1)*3+10/2))*2"
    exp = input()
    calculate(exp)

递归调用

算法实践:表达式求值算法实践:表达式求值

#表达式
def expression_value():
    global i
    a=term_value()
    if i==len(s):
        return a
    c=s[i]
    while c in '+-':
        i+=1
        b=term_value()
        if c=='+':
            a+=b
        else:
            a-=b
        if i==len(s):
            return a
        else:
            c=s[i]
            if c==')':
                i+=1
                return a
    return a
#项
def term_value():
    global i
    a=factor_value()
    if i==len(s):
        return a 
    c=s[i]
    while c in '*/':
        i+=1
        b=term_value()
        if c=='*':
            a*=b
        else:
            a=a//b
        if i==len(s):
            return a 
        else:
            c=s[i]
    return a
#因子
def factor_value():
    global i
    if s[i]=='(':
        i+=1
        return expression_value()
    else:
        temp_i=i 
        while s[i].isdigit():
            i+=1
            if i==len(s):
                break
        return int(s[temp_i:i])
s = input()
i=0
print(expression_value())
相关标签: 算法设计