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

基于栈的中缀算术表达式求值通常是通过逆波兰表示法（Reverse Polish Notation, RPN）来实现的，因为栈数据结构非常适合处理这种操作。在C++中，你可以按照以下步骤进行： 1. **输入转换**：首先，你需要将用户输入的中缀表达式转化为RPN。这通常涉及两个栈：一个用于存储操作数，另一个用于存储运算符。遇到操作数就直接压入操作数栈，遇到运算符则比较其优先级，如果当前栈顶运算符优先级低于新运算符，则依次弹出操作数和运算符，直到找到等于或高于新运算符的，然后将新运算符压入栈中。 2. **计算过程**：遍历操作数堆栈，每次取出两个元素，一个是操作数，另一个是运算符。对这两个操作数应用运算符，并把结果推回栈上。这个过程会一直持续到只剩下一个元素为止，即得到最终的结果。 3. **返回结果**：最后的操作数就是表达式的值。 下面是一个简单的示例代码片段，展示了基本的思路： ```cpp #include <iostream> #include <stack> #include <string> #include <cctype> int precedence(char op) { // 定义运算符的优先级 return op == '+' || op == '-' ? 1 : 2; } bool isOperator(char ch) { return ch == '+' || ch == '-' || ch == '*' || ch == '/'; } std::string infixToRPN(std::string expr) { std::stack<char> ops; std::string result; for (char ch : expr) { if (isdigit(ch)) { result += ch; // 操作数直接添加到结果中 } else if (isOperator(ch)) { while (!ops.empty() && precedence(ops.top()) >= precedence(ch)) { result += ops.top(); ops.pop(); } ops.push(ch); } else if (ch == '(') { ops.push(ch); } else if (ch == ')') { while (ops.top() != '(') { result += ops.top(); ops.pop(); } ops.pop(); // 弹出左括号 } } while (!ops.empty()) { result += ops.top(); ops.pop(); } return result; } int evaluateRPN(std::string rpn) { std::stack<int> stack; for (char ch : rpn) { if (isdigit(ch)) { stack.push(ch - '0'); // 将字符转为数字并压入栈 } else { int right = stack.top(); stack.pop(); int left = stack.top(); stack.pop(); switch (ch) { case '+': stack.push(left + right); break; case '-': stack.push(left - right); break; case '*': stack.push(left * right); break; case '/': stack.push(left / right); break; } } } return stack.top(); // 返回最终结果 } int main() { std::string expr = "4 + 5 * (7 - 9) / 2"; std::string rpn = infixToRPN(expr); int result = evaluateRPN(rpn); std::cout << "Result: " << result << std::endl; return 0; } ```

### 使用栈实现中缀算术表达式求值 为了实现在 C 语言中的中缀表达式的求值，可以利用两个栈来完成这一过程：一个是用于保存操作数的操作数栈；另一个则是用来暂存运算符的运算符栈。当遇到左括号时将其压入到运算符栈中，在碰到右括号之前一直解析并执行可能存在的简单运算直到匹配上对应的左括号为止。 #### 主要逻辑流程如下： - 初始化两个空栈 `operandStack` 和 `operatorStack`. - 遍历输入字符串中的每一个字符. - 如果当前字符是一个数字，则读取完整的数值并将该数值推入操作数栈[^3]. - 若为运算符 (+,-,*,/) 或者左右括号，则依据优先级规则处理运算符栈顶元素与新读取到的运算符之间的关系，并适当调整两者的相对位置或者立即计算已有的部分结果[^2]. - 对于相同或更低级别的运算符来说，应该先弹出栈内的运算符并与后续到来的新运算符做比较直至找到更高级别的运算符停止。 - 当遇见左括号 '(' 应立即将其加入运算符栈等待配对; 而对于右括号 ')' 则需持续从运算符栈取出顶部项并作用于最近的一组操作数之上直到碰见相匹配的左括号为之。 - 完成整个遍历之后，如果还有剩余未被使用的运算符存在于栈里边的话也要依次拿出来同剩下的操作数一起参与最后的结果合成工作. 下面给出一段具体的代码示例展示上述算法的具体实现方式: ```c #include <stdio.h> #include <stdlib.h> #include <ctype.h> // Function prototypes int precedence(char op); void applyOperation(int *top1, int *operands, char *top2, char operators[]); float evaluatePostfix(const char*); #define MAX_SIZE 100 int main() { char expression[] = "(7+15)*(23-28/4)"; printf("Result of '%s' is %f\n", expression, evaluatePostfix(expression)); return 0; } /* Helper function to check operator's priority */ int precedence(char op){ switch(op){ case '+': case '-': return 1; case '*': case '/': return 2; default : return 0; } } /* Evaluate the postfix expression using two stacks */ float evaluatePostfix(const char* exp){ float operands[MAX_SIZE]; char operators[MAX_SIZE]; int top1=-1,top2=-1,i=0; while (exp[i]!='\0'){ if(isdigit(exp[i])){ // Extract full number and push it onto operand stack float num=0; while((isdigit(exp[i]) || exp[i]=='.') && exp[i]!='\0') sscanf(&exp[i++],"%f",&num); operands[++top1]=num; }else{ if(exp[i]=='(') operators[++top2]='('; else if(exp[i]==')'){ while(top2!=-1 && operators[top2]!='(') applyOperation(&top1,operands,&top2,operators); --top2; // Pop out '(' from stack }else{ while(precedence(operators[top2]) >= precedence(exp[i])) applyOperation(&top1,operands,&top2,operators); operators[++top2]=exp[i]; } } i++; } // Process any remaining operations after end-of-string reached while(top2 != -1 )applyOperation(&top1,operands,&top2,operators); return operands[top1]; } /* Apply an operation by popping values off both stacks */ void applyOperation(int *top1,int *operands,char *top2,char operators[]){ char op = operators[*top2--]; float val2 = operands[*top1--],val1 = operands[*top1]; switch(op){ case '+' : operands[++(*top1)]=(val1 + val2); break; case '-' : operands[++(*top1)]=(val1 - val2); break; case '*' : operands[++(*top1)]=(val1 * val2); break; case '/' : if(val2==0){printf("Error! Division By Zero!"); exit(-1);} else {operands[++(*top1)]=(val1 / val2);}break; } } ``` 此段代码实现了基本的功能需求，即通过构建两个独立的数据容器（数组形式模拟），按照既定策略逐步解析给定的数学公式串最终得出确切答案[^4].