c语言实现栈的表达式求值

栈可以用来实现表达式求值。下面是一种基于栈的表达式求值方法的 C 语言实现：

#include <stdio.h>
#include <stdlib.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 item) {
    if (is_full(s)) {
        printf("Error: stack is full\n");
        exit(EXIT_FAILURE);
    }
    s->top++;
    s->data[s->top] = item;
}

int pop(Stack *s) {
    if (is_empty(s)) {
        printf("Error: stack is empty\n");
        exit(EXIT_FAILURE);
    }
    int item = s->data[s->top];
    s->top--;
    return item;
}

int peek(Stack *s) {
    if (is_empty(s)) {
        printf("Error: stack is empty\n");
        exit(EXIT_FAILURE);
    }
    return s->data[s->top];
}

int is_operator(char c) {
    return c == '+' || c == '-' || c == '*' || c == '/';
}

int evaluate(int operand1, int operand2, char operator) {
    switch (operator) {
        case '+':
            return operand1 + operand2;
        case '-':
            return operand1 - operand2;
        case '*':
            return operand1 * operand2;
        case '/':
            return operand1 / operand2;
        default:
            printf("Error: invalid operator\n");
            exit(EXIT_FAILURE);
    }
}

int evaluate_expression(char *expression) {
    Stack operand_stack;
    Stack operator_stack;
    init_stack(&operand_stack);
    init_stack(&operator_stack);

    for (int i = 0; expression[i] != '\0'; i++) {
        char c = expression[i];
        if (c == '(') {
            push(&operator_stack, c);
        } else if (c == ')') {
            while (peek(&operator_stack) != '(') {
                char op = pop(&operator_stack);
                int operand2 = pop(&operand_stack);
                int operand1 = pop(&operand_stack);
                int result = evaluate(operand1, operand2, op);
                push(&operand_stack, result);
            }
            pop(&operator_stack);  // pop the '('
        } else if (is_operator(c)) {
            while (!is_empty(&operator_stack) &&
                   peek(&operator_stack) != '(' &&
                   ((c == '*' || c == '/') || (peek(&operator_stack) == '+' || peek(&operator_stack) == '-'))) {
                char op = pop(&operator_stack);
                int operand2 = pop(&operand_stack);
                int operand1 = pop(&operand_stack);
                int result = evaluate(operand1, operand2, op);
                push(&operand_stack, result);
            }
            push(&operator_stack, c);
        } else if (c >= '0' && c <= '9') {
            int operand = c - '0';
            while (expression[i + 1] >= '0' && expression[i + 1] <= '9') {
                operand = operand * 10 + (expression[i + 1] - '0');
                i++;
            }
            push(&operand_stack, operand);
        }
    }

    while (!is_empty(&operator_stack)) {
        char op = pop(&operator_stack);
        int operand2 = pop(&operand_stack);
        int operand1 = pop(&operand_stack);
        int result = evaluate(operand1, operand2, op);
        push(&operand_stack, result);
    }

    return pop(&operand_stack);
}

int main() {
    char expression[] = "((2+3)*4)-5";
    int result = evaluate_expression(expression);
    printf("%s = %d\n", expression, result);
    return 0;
}

该程序定义了一个 `Stack` 结构体，包含一个 `top` 成员变量和一个 `data` 整型数组，用于存储栈的元素。程序实现了栈的基本操作，包括初始化、判断栈是否为空或已满、入栈、出栈和获取栈顶元素等。同时，程序还实现了一个 `is_operator` 函数，用于判断一个字符是否为运算符；一个 `evaluate` 函数，用于计算两个操作数和一个运算符的结果；以及一个 `evaluate_expression` 函数，用于计算一个表达式的值。该函数首先创建两个栈，一个用于存储操作数，另一个用于存储运算符。接着，遍历表达式中的每个字符，根据字符的类型执行不同的操作，包括入栈、出栈、计算和压入栈等。最后，将操作数栈中的最终结果作为函数的返回值。

以上就是一个基于栈的表达式求值方法的 C 语言实现。