用c语言和栈写一个表达式求值
时间: 2023-05-29 19:07:20 浏览: 92
以下是使用C语言和栈实现表达式求值的示例代码:
```c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#define MAX_STACK_SIZE 100
typedef struct {
int top;
int data[MAX_STACK_SIZE];
} Stack;
void init_stack(Stack *s) {
s->top = -1;
}
int is_empty(Stack *s) {
return s->top == -1;
}
int is_full(Stack *s) {
return s->top == MAX_STACK_SIZE - 1;
}
void push(Stack *s, int value) {
if (is_full(s)) {
printf("Stack overflow\n");
exit(EXIT_FAILURE);
}
s->data[++s->top] = value;
}
int pop(Stack *s) {
if (is_empty(s)) {
printf("Stack underflow\n");
exit(EXIT_FAILURE);
}
return s->data[s->top--];
}
int peek(Stack *s) {
if (is_empty(s)) {
printf("Stack is empty\n");
exit(EXIT_FAILURE);
}
return s->data[s->top];
}
int evaluate(char *expression) {
Stack operand_stack;
Stack operator_stack;
init_stack(&operand_stack);
init_stack(&operator_stack);
char *token = strtok(expression, " ");
while (token) {
if (isdigit(token[0])) {
int operand = atoi(token);
push(&operand_stack, operand);
} else if (token[0] == '+' || token[0] == '-') {
while (!is_empty(&operator_stack) && peek(&operator_stack) != '(') {
int op = pop(&operator_stack);
int op2 = pop(&operand_stack);
int op1 = pop(&operand_stack);
if (op == '+') {
push(&operand_stack, op1 + op2);
} else {
push(&operand_stack, op1 - op2);
}
}
push(&operator_stack, token[0]);
} else if (token[0] == '*' || token[0] == '/') {
while (!is_empty(&operator_stack) && (peek(&operator_stack) == '*' || peek(&operator_stack) == '/')) {
int op = pop(&operator_stack);
int op2 = pop(&operand_stack);
int op1 = pop(&operand_stack);
if (op == '*') {
push(&operand_stack, op1 * op2);
} else {
push(&operand_stack, op1 / op2);
}
}
push(&operator_stack, token[0]);
} else if (token[0] == '(') {
push(&operator_stack, token[0]);
} else if (token[0] == ')') {
while (!is_empty(&operator_stack) && peek(&operator_stack) != '(') {
int op = pop(&operator_stack);
int op2 = pop(&operand_stack);
int op1 = pop(&operand_stack);
if (op == '+') {
push(&operand_stack, op1 + op2);
} else {
push(&operand_stack, op1 - op2);
}
}
pop(&operator_stack);
}
token = strtok(NULL, " ");
}
while (!is_empty(&operator_stack)) {
int op = pop(&operator_stack);
int op2 = pop(&operand_stack);
int op1 = pop(&operand_stack);
if (op == '+') {
push(&operand_stack, op1 + op2);
} else if (op == '-') {
push(&operand_stack, op1 - op2);
} else if (op == '*') {
push(&operand_stack, op1 * op2);
} else {
push(&operand_stack, op1 / op2);
}
}
return pop(&operand_stack);
}
int main() {
char expression[100];
printf("Enter an expression: ");
fgets(expression, sizeof(expression), stdin);
expression[strlen(expression) - 1] = '\0'; // remove newline character
int result = evaluate(expression);
printf("Result: %d\n", result);
return 0;
}
```
该代码使用两个栈:一个用于操作数,一个用于操作符。它通过迭代表达式中的每个标记来处理表达式。如果标记是一个数字,则将其作为操作数推送到操作数栈中。如果标记是+或-,则将其推送到操作符栈中,并尝试将操作符栈中的操作符弹出并应用于操作数栈中的操作数,直到操作符栈为空或操作符栈的顶部是左括号。如果标记是*或/,则将其推送到操作符栈中,并尝试将操作符栈中的*或/操作符弹出并应用于操作数栈中的操作数,直到操作符栈为空或操作符栈的顶部是+或-操作符或左括号。如果标记是左括号,则将其推送到操作符栈中。如果标记是右括号,则将操作符栈中的操作符弹出并应用于操作数栈中的操作数,直到遇到左括号。最后,将剩余的操作符从操作符栈中弹出并应用于操作数栈中的操作数,直到操作符栈为空。最终,操作数栈中应该只有一个元素,该元素是表达式的结果。