表达式求值问题

题目要求

求解形如（a+b)((c+d)e+fhg)的简单算术表达式的求值问题。这种表达式只包括加、减、乘、除4种运算符。为了实现表达式求值，可以首先读入原表达式（包括括号）并创建对应二叉树，其次对二叉树进行前序遍历、中序遍历、后续遍历（非递归），并输出逆波兰表达式，最后求解原表达式的值，同时对非法表达式格式能予以判断。用二叉树的结构来存储表达式，后续遍历二叉树即可得到逆波兰表达式。

解决方案

我一开始把这个课题直接扔给了AI GPT大模型，没想到给我带来了意想不到的收获。

1. 读入原表达式并创建对应的二叉树：

• 使用栈来帮助解析表达式并构建表达式树。

• 运算符作为树的根节点，操作数作为叶子节点。

• 括号用于控制树的构建顺序。

2. 遍历二叉树：

• 前序遍历（Preorder Traversal）：根节点 -> 左子树 -> 右子树

• 中序遍历（Inorder Traversal）：左子树 -> 根节点 -> 右子树

• 后序遍历（Postorder Traversal）：左子树 -> 右子树 -> 根节点

• 逆波兰表达式（Postfix Expression）可以通过后序遍历二叉树得到。

3. 求解原表达式的值：

• 解析逆波兰表达式来计算表达式的最终值。

• 使用栈来帮助计算逆波兰表达式的值。

4. 判断非法表达式：

• 检查括号是否匹配。

• 检查运算符和操作数的数量是否合理。

下面是一个简化的Python代码示例，展示如何构建表达式树并计算表达式值：

class TreeNode:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

def is_operator(c):
    return c in "+-*/"

def construct_tree(expression):
    stack = []
    for char in expression:
        if not is_operator(char):
            node = TreeNode(char)
            stack.append(node)
        else:
            node = TreeNode(char)
            node1 = stack.pop()
            node2 = stack.pop()
            node.right = node1
            node.left = node2
            stack.append(node)
    node = stack.pop()
    return node

def inorder_traversal(root):
    if root:
        inorder_traversal(root.left)
        print(root.value, end=' ')
        inorder_traversal(root.right)

def postorder_traversal(root):
    if root:
        postorder_traversal(root.left)
        postorder_traversal(root.right)
        print(root.value, end=' ')

def evaluate_postfix(expression):
    stack = []
    for char in expression:
        if not is_operator(char):
            stack.append(int(char))
        else:
            val1 = stack.pop()
            val2 = stack.pop()
            switch = {
                '+': val2 + val1,
                '-': val2 - val1,
                '*': val2 * val1,
                '/': val2 / val1
            }
            stack.append(switch[char])
    return stack.pop()

# Example usage:
expression = "ab+cde+*fgh*+*"
tree = construct_tree(expression)
print("Inorder Traversal:")
inorder_traversal(tree)
print("\nPostorder Traversal:")
postorder_traversal(tree)
print("\nEvaluating Postfix Expression:")
result = evaluate_postfix(expression)
print("\nResult:", result)

我的思路

简单说下我的思路吧，网上有一些代码，但是和我这个题目要求有点区别，有的用C++写的，我甚至连头文件都看不懂（这就尴尬了==），然后我之前买的一本数据结构书上有一些思路和参考代码。

1. 用户输入中缀表达式
2. 程序将中缀表达式用二叉树的链式存储结构存储下来
3. 前序、中序遍历这颗二叉树，输出对应的前缀、中缀表达式
4. 后续遍历（非递归）这颗二叉树，并把遍历结果存储在顺序栈内，并输出后缀表达式
5. 对后缀表达式进行求值（具体分析可以下载我在文底留下的链接，是我的课程设计报告==）