用C语言栈实现简单表达式求值

以下是使用C语言栈实现简单表达式求值的示例代码：

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

// 定义栈结构
typedef struct Stack {
    int *array;
    int top;
    int capacity;
} Stack;

// 初始化栈
Stack* createStack(int capacity) {
    Stack *stack = (Stack*)malloc(sizeof(Stack));
    stack->array = (int*)malloc(sizeof(int) * capacity);
    stack->top = -1;
    stack->capacity = capacity;
    return stack;
}

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

// 判断栈是否已满
int isFull(Stack *stack) {
    return stack->top == stack->capacity - 1;
}

// 入栈
void push(Stack *stack, int value) {
    if (isFull(stack)) {
        printf("Stack is full\n");
        return;
    }
    stack->top++;
    stack->array[stack->top] = value;
}

// 出栈
int pop(Stack *stack) {
    if (isEmpty(stack)) {
        printf("Stack is empty\n");
        return -1;
    }
    int value = stack->array[stack->top];
    stack->top--;
    return value;
}

// 获取栈顶元素
int peek(Stack *stack) {
    if (isEmpty(stack)) {
        printf("Stack is empty\n");
        return -1;
    }
    return stack->array[stack->top];
}

// 计算表达式
int calculate(int num1, char op, int num2) {
    int result = 0;
    switch (op) {
        case '+': result = num1 + num2; break;
        case '-': result = num1 - num2; break;
        case '*': result = num1 * num2; break;
        case '/': result = num1 / num2; break;
    }
    return result;
}

// 求值
int evaluate(char *expression) {
    Stack *stack = createStack(50);
    int i, num1, num2, result;
    char op;
    for (i = 0; expression[i] != '\0'; i++) {
        // 如果是数字字符，入栈
        if (expression[i] >= '0' && expression[i] <= '9') {
            push(stack, expression[i] - '0');
        }
        // 如果是操作符，弹出两个数字，计算结果，再入栈
        else if (expression[i] == '+' || expression[i] == '-' || expression[i] == '*' || expression[i] == '/') {
            num2 = pop(stack);
            num1 = pop(stack);
            result = calculate(num1, expression[i], num2);
            push(stack, result);
        }
    }
    // 最后栈内只剩一个元素即为结果
    result = pop(stack);
    free(stack->array);
    free(stack);
    return result;
}

int main() {
    char expression[50];
    printf("Enter an expression: ");
    gets(expression);
    int result = evaluate(expression);
    printf("Result: %d\n", result);
    return 0;
}

示例输入：

Enter an expression: 25+3*6-8/2

示例输出：

Result: 35