表达式求值数据结构 c语言

在 C 语言中，表达式求值可以使用栈这种数据结构来实现。具体步骤如下：

1. 定义两个栈：一个操作符栈和一个操作数栈。

2. 从左到右遍历表达式中的每一个元素（数字或者操作符）。

3. 如果当前元素是数字，就将它压入操作数栈。

4. 如果当前元素是操作符，就将它压入操作符栈。

5. 每当遇到一个操作符时，就从操作数栈中弹出两个元素，进行相应的计算，并将结果压入操作数栈。

6. 当遍历完整个表达式后，操作数栈中就只剩下一个元素，就是表达式的最终结果。

下面是一个简单的表达式求值的 C 语言代码实现：

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

#define STACK_SIZE 100

typedef enum {false, true} bool;

typedef struct {
    int top;
    char data[STACK_SIZE];
} OperatorStack;

typedef struct {
    int top;
    int data[STACK_SIZE];
} OperandStack;

void initOperatorStack(OperatorStack *s) {
    s->top = -1;
}

void initOperandStack(OperandStack *s) {
    s->top = -1;
}

bool isOperatorStackEmpty(OperatorStack *s) {
    return s->top == -1;
}

bool isOperandStackEmpty(OperandStack *s) {
    return s->top == -1;
}

bool isOperatorStackFull(OperatorStack *s) {
    return s->top == STACK_SIZE - 1;
}

bool isOperandStackFull(OperandStack *s) {
    return s->top == STACK_SIZE - 1;
}

void pushOperatorStack(OperatorStack *s, char c) {
    if (isOperatorStackFull(s)) {
        printf("Operator stack overflow!\n");
        exit(EXIT_FAILURE);
    }
    s->data[++s->top] = c;
}

void pushOperandStack(OperandStack *s, int n) {
    if (isOperandStackFull(s)) {
        printf("Operand stack overflow!\n");
        exit(EXIT_FAILURE);
    }
    s->data[++s->top] = n;
}

char popOperatorStack(OperatorStack *s) {
    if (isOperatorStackEmpty(s)) {
        printf("Operator stack underflow!\n");
        exit(EXIT_FAILURE);
    }
    return s->data[s->top--];
}

int popOperandStack(OperandStack *s) {
    if (isOperandStackEmpty(s)) {
        printf("Operand stack underflow!\n");
        exit(EXIT_FAILURE);
    }
    return s->data[s->top--];
}

int evaluate(char *expr) {
    OperatorStack opstack;
    OperandStack opndstack;
    char *p = expr;

    initOperatorStack(&opstack);
    initOperandStack(&opndstack);

    while (*p != '\0') {
        if (isdigit(*p)) {
            int n = 0;
            while (isdigit(*p)) {
                n = n * 10 + (*p - '0');
                p++;
            }
            pushOperandStack(&opndstack, n);
        } else if (*p == '+' || *p == '-' || *p == '*' || *p == '/') {
            while (!isOperatorStackEmpty(&opstack) && opstack.data[opstack.top] != '(' && (*p == '*' || *p == '/') <= (opstack.data[opstack.top] == '+' || opstack.data[opstack.top] == '-')) {
                int opnd2 = popOperandStack(&opndstack);
                int opnd1 = popOperandStack(&opndstack);
                char op = popOperatorStack(&opstack);
                switch (op) {
                    case '+':
                        pushOperandStack(&opndstack, opnd1 + opnd2);
                        break;
                    case '-':
                        pushOperandStack(&opndstack, opnd1 - opnd2);
                        break;
                    case '*':
                        pushOperandStack(&opndstack, opnd1 * opnd2);
                        break;
                    case '/':
                        pushOperandStack(&opndstack, opnd1 / opnd2);
                        break;
                }
            }
            pushOperatorStack(&opstack, *p);
            p++;
        } else if (*p == '(') {
            pushOperatorStack(&opstack, *p);
            p++;
        } else if (*p == ')') {
            while (opstack.data[opstack.top] != '(') {
                int opnd2 = popOperandStack(&opndstack);
                int opnd1 = popOperandStack(&opndstack);
                char op = popOperatorStack(&opstack);
                switch (op) {
                    case '+':
                        pushOperandStack(&opndstack, opnd1 + opnd2);
                        break;
                    case '-':
                        pushOperandStack(&opndstack, opnd1 - opnd2);
                        break;
                    case '*':
                        pushOperandStack(&opndstack, opnd1 * opnd2);
                        break;
                    case '/':
                        pushOperandStack(&opndstack, opnd1 / opnd2);
                        break;
                }
            }
            popOperatorStack(&opstack);
            p++;
        } else {
            p++;
        }
    }

    while (!isOperatorStackEmpty(&opstack)) {
        int opnd2 = popOperandStack(&opndstack);
        int opnd1 = popOperandStack(&opndstack);
        char op = popOperatorStack(&opstack);
        switch (op) {
            case '+':
                pushOperandStack(&opndstack, opnd1 + opnd2);
                break;
            case '-':
                pushOperandStack(&opndstack, opnd1 - opnd2);
                break;
            case '*':
                pushOperandStack(&opndstack, opnd1 * opnd2);
                break;
            case '/':
                pushOperandStack(&opndstack, opnd1 / opnd2);
                break;
        }
    }

    return popOperandStack(&opndstack);
}

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