利用栈实现表达式的求值C语言
时间: 2024-06-13 15:09:39 浏览: 77
用栈实现表达式的求值
利用栈实现表达式的求值C语言可以按照以下步骤进行:
1. 定义两个栈,一个用于存储运算符,一个用于存储操作数和中间结果。
```c
#define MAXSIZE 100
typedef struct {
int data[MAXSIZE];
int top;
} Stack;
void InitStack(Stack *s) {
s->top = -1;
}
int Push(Stack *s, int x) {
if (s->top == MAXSIZE - 1) {
return 0;
}
s->data[++s->top] = x;
return 1;
}
int Pop(Stack *s) {
if (s->top == -1) {
return 0;
}
return s->data[s->top--];
}
int GetTop(Stack *s) {
if (s->top == -1) {
return 0;
}
return s->data[s->top];
}
```
2. 定义一个运算符优先级表,用于比较运算符的优先级。
```c
int priority(char op) {
switch (op) {
case '+':
case '-':
return 1;
case '*':
case '/':
return 2;
case '(':
return 0;
}
return -1;
}
```
3. 读入表达式并进行求值。
```c
int EvaluateExpression(char *exp) {
Stack optr, opnd;
InitStack(&optr);
InitStack(&opnd);
Push(&optr, '(');
int i = 0;
while (exp[i] != '\0') {
if (exp[i] >= '0' && exp[i] <= '9') {
int num = 0;
while (exp[i] >= '0' && exp[i] <= '9') {
num = num * 10 + exp[i] - '0';
i++;
}
Push(&opnd, num);
} else if (exp[i] == '+' || exp[i] == '-' || exp[i] == '*' || exp[i] == '/') {
while (priority(exp[i]) <= priority(GetTop(&optr))) {
int b = Pop(&opnd);
int a = Pop(&opnd);
char op = Pop(&optr);
int result;
switch (op) {
case '+':
result = a + b;
break;
case '-':
result = a - b;
break;
case '*':
result = a * b;
break;
case '/':
result = a / b;
break;
}
Push(&opnd, result);
}
Push(&optr, exp[i]);
i++;
} else if (exp[i] == '(') {
Push(&optr, exp[i]);
i++;
} else if (exp[i] == ')') {
while (GetTop(&optr) != '(') {
int b = Pop(&opnd);
int a = Pop(&opnd);
char op = Pop(&optr);
int result;
switch (op) {
case '+':
result = a + b;
break;
case '-':
result = a - b;
break;
case '*':
result = a * b;
break;
case '/':
result = a / b;
break;
}
Push(&opnd, result);
}
Pop(&optr);
i++;
} else {
i++;
}
}
while (GetTop(&optr) != '(') {
int b = Pop(&opnd);
int a = Pop(&opnd);
char op = Pop(&optr);
int result;
switch (op) {
case '+':
result = a + b;
break;
case '-':
result = a - b;
break;
case '*':
result = a * b;
break;
case '/':
result = a / b;
break;
}
Push(&opnd, result);
}
return GetTop(&opnd);
}
```
4. 调用函数进行表达式求值。
```c
char exp[] = "3+4*5-(6*2+1)";
int result = EvaluateExpression(exp);
printf("%d\n", result); // 输出:10
```
阅读全文