利用栈实现表达式求值c++代码

以下是利用栈实现表达式求值的 C 代码：

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

#define MAX_STACK_SIZE 100

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

void initStack(Stack *s) {
    s->top = -1;
}

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

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

void push(Stack *s, int value) {
    if (isFull(s)) {
        printf("Stack is full!\n");
        exit(1);
    }
    s->data[++s->top] = value;
}

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

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

int evaluate(char *expr) {
    Stack operandStack;
    initStack(&operandStack);

    Stack operatorStack;
    initStack(&operatorStack);

    int i = 0;
    while (expr[i] != '\0') {
        if (isdigit(expr[i])) {
            int value = 0;
            while (isdigit(expr[i])) {
                value = value * 10 + (expr[i] - '0');
                i++;
            }
            push(&operandStack, value);
        } else if (expr[i] == '+' || expr[i] == '-' || expr[i] == '*' || expr[i] == '/') {
            while (!isEmpty(&operatorStack) && peek(&operatorStack) != '(' && ((expr[i] == '*' || expr[i] == '/') || (expr[i] == '+' || expr[i] == '-') && (peek(&operatorStack) == '*' || peek(&operatorStack) == '/'))) {
                int op1 = pop(&operandStack);
                int op2 = pop(&operandStack);
                char op = pop(&operatorStack);
                int result;
                switch (op) {
                    case '+':
                        result = op2 + op1;
                        break;
                    case '-':
                        result = op2 - op1;
                        break;
                    case '*':
                        result = op2 * op1;
                        break;
                    case '/':
                        result = op2 / op1;
                        break;
                }
                push(&operandStack, result);
            }
            push(&operatorStack, expr[i]);
            i++;
        } else if (expr[i] == '(') {
            push(&operatorStack, expr[i]);
            i++;
        } else if (expr[i] == ')') {
            while (!isEmpty(&operatorStack) && peek(&operatorStack) != '(') {
                int op1 = pop(&operandStack);
                int op2 = pop(&operandStack);
                char op = pop(&operatorStack);
                int result;
                switch (op) {
                    case '+':
                        result = op2 + op1;
                        break;
                    case '-':
                        result = op2 - op1;
                        break;
                    case '*':
                        result = op2 * op1;
                        break;
                    case '/':
                        result = op2 / op1;
                        break;
                }
                push(&operandStack, result);
            }
            if (!isEmpty(&operatorStack) && peek(&operatorStack) == '(') {
                pop(&operatorStack);
            }
            i++;
        } else {
            printf("Invalid character: %c\n", expr[i]);
            exit(1);
        }
    }

    while (!isEmpty(&operatorStack)) {
        int op1 = pop(&operandStack);
        int op2 = pop(&operandStack);
        char op = pop(&operatorStack);
        int result;
        switch (op) {
            case '+':
                result = op2 + op1;
                break;
            case '-':
                result = op2 - op1;
                break;
            case '*':
                result = op2 * op1;
                break;
            case '/':
                result = op2 / op1;
                break;
        }
        push(&operandStack, result);
    }

    return pop(&operandStack);
}

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

注意：这段代码只能处理整数的四则运算表达式，不支持浮点数和括号内的表达式优先级。