c语言表达式求值（使用栈）

C语言中使用栈来求解表达式的值是一种常见的方法。栈是一种后进先出（LIFO）的数据结构，可以用来保存运算符和操作数，并按照一定的规则进行入栈和出栈操作。

下面是一个简单的示例，演示了如何使用栈来求解中缀表达式的值：

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

// 定义栈的结构
typedef struct {
    int top; // 栈顶指针
    int capacity; // 栈的容量
    int* array; // 存储元素的数组
} Stack;

// 创建一个栈
Stack* createStack(int capacity) {
    Stack* stack = (Stack*)malloc(sizeof(Stack));
    stack->top = -1;
    stack->capacity = capacity;
    stack->array = (int*)malloc(stack->capacity * sizeof(int));
    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 item) {
    if (isFull(stack)) {
        printf("栈已满，无法入栈\n");
        return;
    }
    stack->array[++stack->top] = item;
}

// 出栈操作
int pop(Stack* stack) {
    if (isEmpty(stack)) {
        printf("栈为空，无法出栈\n");
        return -1;
    }
    return stack->array[stack->top--];
}

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

// 判断字符是否为运算符
int isOperator(char ch) {
    return ch == '+' || ch == '-' || ch == '*' || ch == '/';
}

// 获取运算符的优先级
int getPriority(char ch) {
    if (ch == '+' || ch == '-') {
        return 1;
    } else if (ch == '*' || ch == '/') {
        return 2;
    }
    return 0;
}

// 执行运算
int performOperation(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:
            return 0;
    }
}

// 求解中缀表达式的值
int evaluateExpression(char* expression) {
    Stack* operandStack = createStack(strlen(expression));
    Stack* operatorStack = createStack(strlen(expression));

    for (int i = 0; i < strlen(expression); i++) {
        if (expression[i] == ' ') {
            continue;
        } else if (isdigit(expression[i])) {
            int operand = 0;
            while (i < strlen(expression) && isdigit(expression[i])) {
                operand = operand * 10 + (expression[i] - '0');
                i++;
            }
            i--;
            push(operandStack, operand);
        } else if (isOperator(expression[i])) {
            while (!isEmpty(operatorStack) && getPriority(peek(operatorStack)) >= getPriority(expression[i])) {
                int operand2 = pop(operandStack);
                int operand1 = pop(operandStack);
                char operator = pop(operatorStack);
                int result = performOperation(operand1, operand2, operator);
                push(operandStack, result);
            }
            push(operatorStack, expression[i]);
        } else if (expression[i] == '(') {
            push(operatorStack, expression[i]);
        } else if (expression[i] == ')') {
            while (!isEmpty(operatorStack) && peek(operatorStack) != '(') {
                int operand2 = pop(operandStack);
                int operand1 = pop(operandStack);
                char operator = pop(operatorStack);
                int result = performOperation(operand1, operand2, operator);
                push(operandStack, result);
            }
            pop(operatorStack); // 弹出左括号
        }
    }

    while (!isEmpty(operatorStack)) {
        int operand2 = pop(operandStack);
        int operand1 = pop(operandStack);
        char operator = pop(operatorStack);
        int result = performOperation(operand1, operand2, operator);
        push(operandStack, result);
    }

    int finalResult = pop(operandStack);
    free(operandStack);
    free(operatorStack);
    return finalResult;
}

int main() {
    char expression[100];
    printf("请输入中缀表达式：");
    fgets(expression, sizeof(expression), stdin);
    int result = evaluateExpression(expression);
    printf("表达式的值为：%d\n", result);
    return 0;
}

这段代码演示了如何使用栈来求解中缀表达式的值。它首先定义了一个栈的结构，然后实现了栈的基本操作，包括创建栈、判断栈是否为空、判断栈是否已满、入栈操作、出栈操作和获取栈顶元素。接下来，它定义了一些辅助函数，用于判断字符是否为运算符、获取运算符的优先级和执行运算。最后，它实现了求解中缀表达式的函数，该函数使用两个栈来保存操作数和运算符，并按照一定的规则进行入栈和出栈操作，最终得到表达式的值。