基于栈的中缀算术表达式求值c语言
时间: 2024-10-07 08:01:08 浏览: 38
基于栈的数据结构可以在C语言中用于计算中缀表达式的值,也称为逆波兰表示法(RPN)。这种技术利用了栈的特点:后进先出(LIFO)。以下是基本步骤:
1. **输入处理**:遍历中缀表达式的每个字符,如果是数字则压入栈,如果是运算符则执行操作。
2. **运算符处理**:
- 如果遇到运算符,取出栈顶两个元素(如果有两个),进行相应的运算(如加、减、乘、除),并将结果替换这两个元素,然后将运算结果放回栈顶。
- 如果栈顶只有一个元素,或者遇到优先级更低的运算符,则直接将当前运算符压入栈。
3. **结束处理**:当遍历完所有字符后,栈顶剩余的就是最终的结果。
```c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct {
char op; // 运算符
} Token;
int isOperator(char c) {
return (c == '+' || c == '-' || c == '*' || c == '/');
}
double applyOp(double a, double b, char op) {
switch (op) {
case '+': return a + b;
case '-': return a - b;
case '*': return a * b;
case '/': if (b != 0) return a / b; else return 0; // 防止除数为零
}
}
double evaluateRPN(char* tokens) {
int length = strlen(tokens);
Token stack[length]; // 栈大小等于表达式长度
int top = -1; // 栈顶指针初始化为-1
for (int i = 0; i < length; ++i) {
if (!isOperator(tokens[i])) { // 数字
stack[++top].op = tokens[i] - '0'; // 把数字转换成整数并压入栈
} else { // 运算符
while (top >= 0 && isOperator(stack[top].op)) { // 找到最近的左括号
double val2 = stack[top].op;
top--;
double val1 = stack[top].op;
stack[top].op = applyOp(val1, val2, stack[top].op); // 计算并更新栈顶元素
}
stack[++top].op = tokens[i];
}
}
// 最后的两个元素是结果
return applyOp(stack[top].op, stack[top - 1].op, stack[top].op);
}
int main() {
char expr[] = "2 3 + 4 *";
printf("Result: %.2f\n", evaluateRPN(expr));
return 0;
}
```