c语言:使用栈设计一个算术表达式求值程序
时间: 2024-10-18 08:08:07 浏览: 80
在C语言中,使用栈数据结构设计一个算术表达式求值程序通常涉及到递归下降解析法(Recursive Descent Parsing),或者更简单一点,我们可以使用前缀或后缀(逆波兰)表示法。这里我会描述一种基于后缀表示法(也称为逆波兰表示法)的方法。
首先,你需要创建两个栈,一个用于存储操作数,另一个用于临时计算结果:
```c
#include <stdio.h>
#include <stdlib.h>
#include <stack>
typedef struct {
double value;
} ValueStack;
typedef struct {
char token;
ValueStack *values;
int top;
} ExpressionStack;
// 函数原型
double evaluate(char* expression);
```
接下来,定义一些辅助函数,包括处理运算符、数字和结束符的行为:
1. `push_number`:将数字压入值栈。
2. `is_operator`:检查字符是否是有效的运算符。
3. `pop_top_numbers`:从值栈弹出足够的数字以匹配当前运算符。
4. `evaluate_token`:处理特定的运算符,如加减乘除。
关键部分是`evaluate`函数,它遍历输入的后缀表达式,利用两个栈进行操作:
```c
double evaluate(char* expression) {
ValueStack values = {0};
ExpressionStack expr_stack;
// 初始化栈顶指针
expr_stack.values = &values;
expr_stack.top = -1;
for (char* ptr = expression; *ptr != '\0'; ++ptr) {
if (isdigit(*ptr)) { // 数字
push_number(ptr, &values);
} else if (*ptr == ' ') {} // 忽略空格
else { // 运算符
while (expr_stack.top >= 0 && is_operator(expr_stack.values->top.token)) {
double b = pop_top_numbers(&values);
double a = pop_top_numbers(&values);
switch (expr_stack.values->top.token) {
case '+':
values.values[expr_stack.top] = a + b;
break;
case '-':
values.values[expr_stack.top] = a - b;
break;
case '*':
values.values[expr_stack.top] = a * b;
break;
case '/':
if (b != 0)
values.values[expr_stack.top] = a / b;
else
printf("Error: Division by zero\n");
break;
default:
printf("Invalid operator: %c\n", expr_stack.values->top.token);
return 0;
}
expr_stack.top--;
}
expr_stack.values->top++;
expr_stack.values->top token = *ptr; // 将运算符推入栈
}
}
// 检查剩余的操作数是否与运算符匹配,如果有,则执行相应的运算
while (expr_stack.top >= 0 && is_operator(expr_stack.values->top.token)) {
double b = pop_top_numbers(&values);
double a = pop_top_numbers(&values);
// ... 同样处理剩下的运算
}
return values.values[0]; // 返回最终结果
}
// 辅助函数...
```
阅读全文