用栈实现算法表达求值的c程序

当使用栈来实现算法表达式求值时，可以按照以下步骤进行：

1. 创建两个栈，一个用于存储操作数，另一个用于存储操作符。
2. 从左到右遍历算法表达式的每个字符。
3. 如果当前字符是数字，则将其转换为操作数，并将其压入操作数栈。
4. 如果当前字符是操作符，则进行以下操作：
- 如果操作符栈为空，或者当前操作符的优先级大于栈顶操作符的优先级，则将当前操作符压入操作符栈。
- 否则，从操作数栈中弹出两个操作数，从操作符栈中弹出一个操作符，进行运算，并将结果压入操作数栈。
5. 当遍历完整个表达式后，如果操作符栈不为空，则从操作数栈中弹出两个操作数，从操作符栈中弹出一个操作符，进行运算，并将结果压入操作数栈。
6. 最后，操作数栈中的唯一元素即为表达式的求值结果。

下面是一个用C语言实现的示例代码：

#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(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 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:
            printf("无效的操作符\n");
            return -1;
    }
}

// 表达式求值函数
int evaluateExpression(char* expression) {
    Stack* operandStack = createStack(strlen(expression));
    Stack* operatorStack = createStack(strlen(expression));

    for (int i = 0; expression[i] != '\0'; i++) {
        if (expression[i] >= '0' && expression[i] <= '9') {
            int operand = 0;
            while (expression[i] >= '0' && expression[i] <= '9') {
                operand = operand * 10 + (expression[i] - '0');
                i++;
            }
            push(operandStack, operand);
            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);
            }
            if (!isEmpty(operatorStack) && peek(operatorStack) == '(') {
                pop(operatorStack);
            } else {
                printf("表达式括号不匹配\n");
                return -1;
            }
        } else if (expression[i] == '+' || expression[i] == '-' || expression[i] == '*' || expression[i] == '/') {
            while (!isEmpty(operatorStack) && peek(operatorStack) != '(' &&
                   ((expression[i] != '*' && expression[i] != '/') ||
                    (peek(operatorStack) != '+' && peek(operatorStack) != '-'))) {
                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]);
        }
    }

    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("请输入要求值的算法表达式：");
    scanf("%s", expression);

    int result = evaluateExpression(expression);
    printf("表达式的求值结果为：%d\n", result);

    return 0;
}