第1关 基于栈的中缀算术表达式求值

栈是一种后进先出（LIFO）的数据结构，可以用来处理中缀算术表达式求值。具体的算法流程如下： 1. 定义两个栈，一个用来存放操作数，一个用来存放操作符。 2. 从左到右遍历中缀表达式的每个字符，对于每个字符执行以下操作： 1. 如果是数字，直接压入操作数栈。 2. 如果是左括号，直接压入操作符栈。 3. 如果是右括号，则一直从操作符栈中弹出操作符，并从操作数栈中弹出相应的操作数，直到遇到左括号为止。将弹出的操作数和操作符进行运算，将结果再压入操作数栈。 4. 如果是操作符，则首先比较它的优先级和操作符栈顶元素的优先级。如果它的优先级较高或者操作符栈为空，则直接压入操作符栈，否则从操作符栈中弹出操作符，并从操作数栈中弹出相应的操作数，将它们进行运算，将结果再压入操作数栈。然后将当前操作符压入操作符栈。 3. 重复执行步骤2，直到处理完所有的字符。 4. 当操作符栈不为空时，一直从操作符栈中弹出操作符，并从操作数栈中弹出相应的操作数，将它们进行运算，将结果再压入操作数栈。 5. 最后操作数栈中只剩下一个元素，就是表达式的值。 以下为Python代码实现： ``` python def infix_eval(expression): # 定义操作符优先级 priority = {'+': 1, '-': 1, '*': 2, '/': 2, '(': 0, ')': 0} # 定义操作数栈和操作符栈 operands = [] operators = [] # 开始遍历中缀表达式 for char in expression: if char.isdigit(): operands.append(int(char)) elif char == '(': operators.append(char) elif char == ')': while operators[-1] != '(': op = operators.pop() b = operands.pop() a = operands.pop() result = eval(str(a) + op + str(b)) operands.append(result) operators.pop() elif char in priority: while operators and priority[char] <= priority[operators[-1]]: op = operators.pop() b = operands.pop() a = operands.pop() result = eval(str(a) + op + str(b)) operands.append(result) operators.append(char) # 处理剩余的操作符 while operators: op = operators.pop() b = operands.pop() a = operands.pop() result = eval(str(a) + op + str(b)) operands.append(result) return operands[0] ``` 可以测试以下代码： ``` python expression = '3+4*5-(2+3*2)' result = infix_eval(expression) print(f'{expression} = {result}') ``` 输出结果： ``` 3+4*5-(2+3*2) = 13 ```

#include <stdio.h> #include <stdlib.h> /* 栈结构体 */ typedef struct stack { int top; int capacity; int *array; } Stack; /* 创建栈 */ Stack *createStack(int capacity) { Stack *stack = (Stack *)malloc(sizeof(Stack)); stack->top = -1; stack->capacity = capacity; stack->array = (int *)malloc(stack->capacity * sizeof(int)); return stack; } /* 判断栈是否已满 */ int isFull(Stack *stack) { return stack->top == stack->capacity - 1; } /* 判断栈是否为空 */ int isEmpty(Stack *stack) { return stack->top == -1; } /* 压栈 */ void push(Stack *stack, int item) { if (isFull(stack)) { printf("Stack is full\n"); return; } stack->array[++stack->top] = item; } /* 出栈 */ int pop(Stack *stack) { if (isEmpty(stack)) { printf("Stack is empty\n"); return -1; } return stack->array[stack->top--]; } /* 获取栈顶元素 */ int peek(Stack *stack) { if (isEmpty(stack)) return -1; return stack->array[stack->top]; } /* 操作符优先级 */ int precedence(char ch) { switch (ch) { case '+': case '-': return 1; case '*': case '/': return 2; case '^': return 3; default: return -1; } } /* 中缀表达式求值 */ int evaluate(char *exp) { Stack *operands = createStack(strlen(exp)); Stack *operators = createStack(strlen(exp)); for (int i = 0; exp[i]; ++i) { if (exp[i] == ' ') continue; else if (isdigit(exp[i])) { int num = 0; while (isdigit(exp[i])) { num = num * 10 + (exp[i] - '0'); ++i; } --i; push(operands, num); } else if (exp[i] == '(') push(operators, exp[i]); else if (exp[i] == ')') { while (!isEmpty(operators) && peek(operators) != '(') { int op1 = pop(operands); int op2 = pop(operands); char op = pop(operators); switch (op) { case '+': push(operands, op2 + op1); break; case '-': push(operands, op2 - op1); break; case '*': push(operands, op2 * op1); break; case '/': push(operands, op2 / op1); break; case '^': push(operands, pow(op2, op1)); break; } } if (!isEmpty(operators) && peek(operators) == '(') pop(operators); } else { while (!isEmpty(operators) && precedence(exp[i]) <= precedence(peek(operators))) { int op1 = pop(operands); int op2 = pop(operands); char op = pop(operators); switch (op) { case '+': push(operands, op2 + op1); break; case '-': push(operands, op2 - op1); break; case '*': push(operands, op2 * op1); break; case '/': push(operands, op2 / op1); break; case '^': push(operands, pow(op2, op1)); break; } } push(operators, exp[i]); } } while (!isEmpty(operators)) { int op1 = pop(operands); int op2 = pop(operands); char op = pop(operators); switch (op) { case '+': push(operands, op2 + op1); break; case '-': push(operands, op2 - op1); break; case '*': push(operands, op2 * op1); break; case '/': push(operands, op2 / op1); break; case '^': push(operands, pow(op2, op1)); break; } } return pop(operands); } int main() { char exp[] = "3 + 4 * ( 5 - 2 ) ^ 2"; printf("结果为：%d\n", evaluate(exp)); return 0; }