利用栈实现表达式求值C语言版

好的，以下是一个简单的栈实现表达式求值的C语言代码：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>

#define STACK_SIZE 100

// 定义栈结构体
typedef struct {
    int top;
    int data[STACK_SIZE];
} Stack;

// 初始化栈
void init(Stack *s) {
    s->top = -1;
}

// 判断栈是否为空
int is_empty(Stack *s) {
    return s->top == -1;
}

// 判断栈是否已满
int is_full(Stack *s) {
    return s->top == STACK_SIZE - 1;
}

// 入栈
void push(Stack *s, int x) {
    if (is_full(s)) {
        printf("Stack overflow!\n");
        exit(1);
    }
    s->top++;
    s->data[s->top] = x;
}

// 出栈
int pop(Stack *s) {
    if (is_empty(s)) {
        printf("Stack underflow!\n");
        exit(1);
    }
    int x = s->data[s->top];
    s->top--;
    return x;
}

// 获取栈顶元素
int peek(Stack *s) {
    if (is_empty(s)) {
        printf("Stack empty!\n");
        exit(1);
    }
    return s->data[s->top];
}

// 判断字符是否为操作符
int is_operator(char c) {
    return c == '+' || c == '-' || c == '*' || c == '/';
}

// 获取操作符的优先级
int precedence(char c) {
    if (c == '+' || c == '-') {
        return 1;
    } else if (c == '*' || c == '/') {
        return 2;
    } else {
        return 0;
    }
}

// 表达式求值
int evaluate(char *expr) {
    Stack num_stack, op_stack;
    init(&num_stack);
    init(&op_stack);
    int len = strlen(expr);
    for (int i = 0; i < len; i++) {
        if (isspace(expr[i])) {
            continue;
        } else if (isdigit(expr[i])) {
            int num = 0;
            while (i < len && isdigit(expr[i])) {
                num = num * 10 + (expr[i] - '0');
                i++;
            }
            i--;
            push(&num_stack, num);
        } else if (is_operator(expr[i])) {
            while (!is_empty(&op_stack) && precedence(peek(&op_stack)) >= precedence(expr[i])) {
                int num2 = pop(&num_stack);
                int num1 = pop(&num_stack);
                char op = pop(&op_stack);
                switch (op) {
                case '+':
                    push(&num_stack, num1 + num2);
                    break;
                case '-':
                    push(&num_stack, num1 - num2);
                    break;
                case '*':
                    push(&num_stack, num1 * num2);
                    break;
                case '/':
                    push(&num_stack, num1 / num2);
                    break;
                }
            }
            push(&op_stack, expr[i]);
        } else {
            printf("Invalid character: %c\n", expr[i]);
            exit(1);
        }
    }
    while (!is_empty(&op_stack)) {
        int num2 = pop(&num_stack);
        int num1 = pop(&num_stack);
        char op = pop(&op_stack);
        switch (op) {
        case '+':
            push(&num_stack, num1 + num2);
            break;
        case '-':
            push(&num_stack, num1 - num2);
            break;
        case '*':
            push(&num_stack, num1 * num2);
            break;
        case '/':
            push(&num_stack, num1 / num2);
            break;
        }
    }
    return pop(&num_stack);
}

// 测试
int main() {
    char expr[100];
    printf("Enter an expression: ");
    fgets(expr, 100, stdin);
    printf("Result: %d\n", evaluate(expr));
    return 0;
}

该代码主要利用了两个栈来实现表达式求值，一个栈用来存储操作数，另一个栈用来存储操作符。遍历表达式字符串，如果遇到数字字符，则将其转换为整数并入操作数栈；如果遇到操作符，则与操作符栈顶元素比较优先级，如果当前操作符优先级较低，则将操作符栈顶元素弹出并将操作数栈顶的两个元素进行计算，结果再入操作数栈。最后，将操作符栈中的剩余操作符依次弹出并进行计算，直到操作符栈为空，最后操作数栈中剩余的元素即为表达式的值。