基于栈的前缀算术表达式求值

### 基于栈的中缀算术表达式求值 基于栈的中缀算术表达式求值是一种经典的算法设计问题，其核心在于利用两个栈分别存储操作数和运算符来处理复杂的优先级关系。以下是该算法的设计思路以及其实现方法。 #### 算法原理 为了直接对中缀表达式进行计算而不将其转换为其他形式（如后缀或前缀），可以采用双栈结构： - **操作数栈**用于保存参与运算的具体数值。 - **运算符栈**用于管理待执行的操作及其优先级顺序。 当解析到一个新的字符时，依据它是数字还是运算符采取不同的动作： 1. 如果当前字符是一个数字，则读取完整的浮点数并压入操作数栈[^1]。 2. 若遇到左括号`(`，则直接推入运算符栈作为边界标记[^2]。 3. 对于右括号`)`，持续弹出运算符栈中的元素直到找到对应的左括号为止，在此过程中完成相应的计算并将结果重新存回操作数栈。 4. 当碰到普通的运算符（加减乘除）时，需比较它与栈顶现有运算符之间的优先级别决定是否立即展开计算或者等待后续更高级别的指令到来后再做进一步判断。 #### 实现细节 下面给出了一种可能的语言实现方式——Python版本： ```python def precedence(op): """定义各运算符的优先级""" if op in ('+', '-'): return 1 elif op in ('*', '/'): return 2 else: # '(' or ')' return 0 def apply_operation(a, b, operator): """应用指定运算符至a,b两数上""" if operator == '+': return a + b elif operator == '-': return a - b elif operator == '*': return a * b elif operator == '/': if b != 0: return a / b raise ZeroDivisionError('Cannot divide by zero') def evaluate(expression): numbers = [] # 存储操作数 operators = [] # 存储运算符 i = 0 # 遍历索引初始化 while i < len(expression): char = expression[i] if char.isdigit() or (char == '.' and any(c.isdigit() for c in expression[i:i+2])): num_str = "" decimal_found = False # 提取出整个连续的数字串 while i < len(expression) and ((expression[i].isdigit()) or (expression[i]=='.')): if expression[i]=='.':decimal_found=True num_str += expression[i] i+=1 number=float(num_str) if not(decimal_found)and int(number)==number:number=int(number)# 整形化整型数据 numbers.append(number) elif char == '(': operators.append(char) elif char == ')': while operators[-1] != '(': val2 = numbers.pop() val1 = numbers.pop() operation = operators.pop() result = apply_operation(val1, val2, operation) numbers.append(result) operators.pop() # 移除'(' elif char in "+-*/": while (operators and operators[-1]!='(' and precedence(operators[-1]) >= precedence(char)): val2 = numbers.pop() val1 = numbers.pop() operation = operators.pop() result = apply_operation(val1, val2, operation) numbers.append(result) operators.append(char) i += 1 while operators: val2 = numbers.pop() val1 = numbers.pop() operation = operators.pop() result = apply_operation(val1, val2, operation) numbers.append(result) return numbers[0] # 测试样例 expr = "3 + (5.5 * 2) - 8" print(f"The value of '{expr}' is {evaluate(expr)}") #[^1] ``` 上述代码实现了基本功能，并通过函数封装提高了可维护性和扩展性。注意这里假设输入字符串已经经过适当清理去除空白字符等干扰因素。 #### 注意事项 - 处理异常情况非常重要，比如非法输入、除零错误等情况都应在实际部署环境中加以考虑。 - 此外还需确保所有使用的库均支持所需的精度范围以满足题目对于double类型的约束条件.

存储结构定义如下： （1）基于栈的中缀算术表达式求值 // 定义栈结构 typedef struct Stack { int top; // 栈顶指针 double data[MAXSIZE]; // 栈中元素 } Stack; // 初始化栈 void initStack(Stack *s); // 判断栈是否为空 int isEmpty(Stack *s); // 判断栈是否已满 int isFull(Stack *s); // 元素入栈 void push(Stack *s, double x); // 元素出栈 double pop(Stack *s); // 获取栈顶元素 double getTop(Stack *s); // 中缀表达式求值 double evaluate(char *exp, Stack *numStack, Stack *opStack); （2）基于栈的后缀算术表达式求值 // 定义栈结构 typedef struct Stack { int top; // 栈顶指针 int data[MAXSIZE]; // 栈中元素 } Stack; // 初始化栈 void initStack(Stack *s); // 判断栈是否为空 int isEmpty(Stack *s); // 判断栈是否已满 int isFull(Stack *s); // 元素入栈 void push(Stack *s, int x); // 元素出栈 int pop(Stack *s); // 获取栈顶元素 int getTop(Stack *s); // 中缀表达式转后缀表达式 void infixToPostfix(char *infixExp, char *postfixExp); // 后缀表达式求值 int evaluate(char *postfixExp); （3）基于二叉树的算术表达式求值 // 定义二叉树结构 typedef struct TreeNode { char data; // 结点数据，可能是操作符或操作数 struct TreeNode *left; // 左子树 struct TreeNode *right; // 右子树 } TreeNode; // 创建二叉树 TreeNode *createExpressionTree(char *exp); // 中序遍历二叉树 void inOrder(TreeNode *root, Stack *s); // 表达式树求值 int evaluate(TreeNode *root); // 初始化栈 void initStack(Stack *s); // 判断栈是否为空 int isEmpty(Stack *s); // 判断栈是否已满 int isFull(Stack *s); // 元素入栈 void push(Stack *s, int x); // 元素出栈 int pop(Stack *s); // 获取栈顶元素 int getTop(Stack *s);