c语言利用栈实现表达式求值基础耿国华

栈是一种后进先出（LIFO）的数据结构，它可以用于计算表达式的值。在使用栈求解表达式时，我们需要遵循以下步骤：

1. 创建两个栈：一个用于存储操作数，一个用于存储运算符；
2. 遍历表达式，如果遇到操作数，则将其压入操作数栈中；
3. 如果遇到运算符，则将其与运算符栈的栈顶元素比较，如果该运算符的优先级大于栈顶运算符的优先级，则将该运算符压入运算符栈中；否则，将运算符栈的栈顶元素弹出，将操作数栈的栈顶两个元素弹出，进行计算，并将结果压入操作数栈中，直到该运算符的优先级大于栈顶运算符的优先级；
4. 重复步骤2~3，直到表达式遍历完毕；
5. 将操作数栈中最后剩余的元素进行计算，得到表达式的值。

以下是一个简单的实现：

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

#define MAX_SIZE 100

typedef struct {
    int data[MAX_SIZE];
    int top;
} Stack;

void push(Stack *s, int x) {
    if (s->top == MAX_SIZE - 1) {
        printf("Stack Overflow\n");
        exit(1);
    }
    s->data[++(s->top)] = x;
}

int pop(Stack *s) {
    if (s->top == -1) {
        printf("Stack Underflow\n");
        exit(1);
    }
    return s->data[(s->top)--];
}

int is_empty(Stack *s) {
    return s->top == -1;
}

int peek(Stack *s) {
    if (s->top == -1) {
        printf("Stack Underflow\n");
        exit(1);
    }
    return s->data[s->top];
}

int precedence(char op) {
    switch (op) {
        case '+':
        case '-':
            return 1;
        case '*':
        case '/':
            return 2;
        case '^':
            return 3;
        default:
            return -1;
    }
}

int evaluate_expression(char *expr) {
    Stack operand_stack, operator_stack;
    operand_stack.top = operator_stack.top = -1;
    int i, val, val1, val2;
    char ch, op;
    for (i = 0; expr[i] != '\0'; i++) {
        ch = expr[i];
        if (ch >= '0' && ch <= '9') {
            val = 0;
            while (ch >= '0' && ch <= '9') {
                val = val * 10 + (ch - '0');
                i++;
                ch = expr[i];
            }
            i--;
            push(&operand_stack, val);
        } else if (ch == '(') {
            push(&operator_stack, ch);
        } else if (ch == ')') {
            while (!is_empty(&operator_stack) && peek(&operator_stack) != '(') {
                val2 = pop(&operand_stack);
                val1 = pop(&operand_stack);
                op = pop(&operator_stack);
                switch (op) {
                    case '+':
                        push(&operand_stack, val1 + val2);
                        break;
                    case '-':
                        push(&operand_stack, val1 - val2);
                        break;
                    case '*':
                        push(&operand_stack, val1 * val2);
                        break;
                    case '/':
                        push(&operand_stack, val1 / val2);
                        break;
                    case '^':
                        push(&operand_stack, val1 ^ val2);
                        break;
                }
            }
            pop(&operator_stack);
        } else if (ch == '+' || ch == '-' || ch == '*' || ch == '/' || ch == '^') {
            while (!is_empty(&operator_stack) && precedence(ch) <= precedence(peek(&operator_stack))) {
                val2 = pop(&operand_stack);
                val1 = pop(&operand_stack);
                op = pop(&operator_stack);
                switch (op) {
                    case '+':
                        push(&operand_stack, val1 + val2);
                        break;
                    case '-':
                        push(&operand_stack, val1 - val2);
                        break;
                    case '*':
                        push(&operand_stack, val1 * val2);
                        break;
                    case '/':
                        push(&operand_stack, val1 / val2);
                        break;
                    case '^':
                        push(&operand_stack, val1 ^ val2);
                        break;
                }
            }
            push(&operator_stack, ch);
        }
    }
    while (!is_empty(&operator_stack)) {
        val2 = pop(&operand_stack);
        val1 = pop(&operand_stack);
        op = pop(&operator_stack);
        switch (op) {
            case '+':
                push(&operand_stack, val1 + val2);
                break;
            case '-':
                push(&operand_stack, val1 - val2);
                break;
            case '*':
                push(&operand_stack, val1 * val2);
                break;
            case '/':
                push(&operand_stack, val1 / val2);
                break;
            case '^':
                push(&operand_stack, val1 ^ val2);
                break;
        }
    }
    return pop(&operand_stack);
}

int main() {
    char expr[MAX_SIZE];
    printf("Enter expression: ");
    fgets(expr, MAX_SIZE, stdin);
    printf("Result: %d\n", evaluate_expression(expr));
    return 0;
}

该程序先定义了一个栈的结构体，并实现了栈的基本操作，包括 push、pop、is_empty 和 peek。接着定义了一个函数 precedence，用于返回运算符的优先级。最后，定义了 evaluate_expression 函数，用于计算表达式的值。该函数遍历表达式，如果遇到操作数，则将其压入操作数栈中；如果遇到左括号，则将其压入运算符栈中；如果遇到右括号，则将运算符栈的元素弹出，将操作数栈的栈顶两个元素弹出，进行计算，并将结果压入操作数栈中，直到遇到左括号；如果遇到运算符，则将其与运算符栈的栈顶元素比较，如果该运算符的优先级大于栈顶运算符的优先级，则将该运算符压入运算符栈中；否则，将运算符栈的栈顶元素弹出，将操作数栈的栈顶两个元素弹出，进行计算，并将结果压入操作数栈中，直到该运算符的优先级大于栈顶运算符的优先级。最后，将操作数栈中最后剩余的元素进行计算，得到表达式的值。