讨论/求职面试/面试题:类似Python的eval()函数实现/
面试题:类似Python的eval()函数实现

某大厂刚考的~

有一些类似这样的字符串"((30 * 2)/(16 + 30))", 你有一个可以调用的接口read.next(),每调用一次会得到字符串中的一个元素,比如调用该方法依次会得到(...(...30...*......16......)...)(带语法解析功能,30会一起输出,而不是3,0或1,6),假设遍历完了会返回'EOS'。请你设计一个函数,调用该接口计算四则运算表达式的值,只能遍历一遍。

12
共 8 个回复

中缀表达式 百度一下一堆解法

4

把值放入二叉树里,root是加减乘除,左右是数字,然后后续遍历计算。树和栈方法自己定义

from binary_tree.base_tree import BinaryTree, Stack
import operator
formula = "( ( 30 * 2 ) / ( 16 + 30 ) )"

def build_parse_tree(input):

    fplist = input.split()
    tree = BinaryTree("")
    stack = Stack()
    stack.push(tree)
    current_tree = tree

    for i in fplist:
        if i == "(":
            current_tree.insert_left("")
            stack.push(current_tree)
            current_tree = current_tree.get_leftchild()
        elif i not in '+-*/)':
            current_tree.set_root(int(i))
            current_tree = stack.pop()
        elif i in '+-*/':
            current_tree.set_root(i)
            current_tree.insert_right("")
            stack.push(current_tree)
            current_tree = current_tree.get_rightchild()
        elif i == ")":
            current_tree = stack.pop()
        else:
            raise ValueError(f"unknown operator {i}")
    return tree

def evaluate(parse_tree):

    opers = {'+': operator.add,
            '-': operator.sub,
            '*': operator.mul,
            '/': operator.truediv}
    if parse_tree:

        left = evaluate(parse_tree.get_leftchild())
        right = evaluate(parse_tree.get_rightchild())
        if left and right:
            fn = opers[parse_tree.get_root()]
            return fn(left, right)
        else:
            return parse_tree.get_root()

tree = build_parse_tree(formula)
result = evaluate(tree)
print(result)
1

转成逆波兰式然后计算就行了,找一本编译原理的书看一下,里面都有相关的方法
力扣上也有类似的题目:224. 基本计算器
这道题只有加减法和括号,没有乘除法,可以参考一下
另外这道题的题解板块里有带乘除法的题解,可以去看看:拆解复杂问题:实现一个完整计算器

1

中序表达式求职,双栈,或者先转换为逆波兰表达式

1

666!

感谢大佬!直接被这道题打回原形。。

感谢。搜了一下,奇怪的知识又增加了。。

懵逼。。能写下伪代码么。。