表达式求值数据结构的代码
时间: 2023-11-16 11:58:27 浏览: 34
以下是用C语言实现表达式求值算法的代码,其中包括了栈的典型应用——后缀表达式求值:
```
#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#define MAX_STACK_SIZE 100
typedef struct {
double data[MAX_STACK_SIZE];
int top;
} Stack;
void initStack(Stack *s) {
s->top = -1;
}
int isEmpty(Stack *s) {
return s->top == -1;
}
int isFull(Stack *s) {
return s->top == MAX_STACK_SIZE - 1;
}
void push(Stack *s, double x) {
if (isFull(s)) {
printf("Stack overflow\n");
exit(1);
}
s->data[++s->top] = x;
}
double pop(Stack *s) {
if (isEmpty(s)) {
printf("Stack underflow\n");
exit(1);
}
return s->data[s->top--];
}
double evaluatePostfix(char *expr) {
Stack s;
double op1, op2, result;
initStack(&s);
while (*expr) {
if (isdigit(*expr)) {
push(&s, *expr - '0');
} else {
op2 = pop(&s);
op1 = pop(&s);
switch (*expr) {
case '+':
result = op1 + op2;
break;
case '-':
result = op1 - op2;
break;
case '*':
result = op1 * op2;
break;
case '/':
result = op1 / op2;
break;
default:
printf("Invalid operator\n");
exit(1);
}
push(&s, result);
}
expr++;
}
return pop(&s);
}
int main() {
char expr[MAX_STACK_SIZE];
printf("Enter a postfix expression: ");
scanf("%s", expr);
printf("Result: %lf\n", evaluatePostfix(expr));
return 0;
}
```