利用栈实现表达式的求值C语言

利用栈实现表达式的求值C语言可以按照以下步骤进行：

1. 定义两个栈，一个用于存储运算符，一个用于存储操作数和中间结果。

#define MAXSIZE 100
typedef struct {
    int data[MAXSIZE];
    int top;
} Stack;

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

int Push(Stack *s, int x) {
    if (s->top == MAXSIZE - 1) {
        return 0;
    }
    s->data[++s->top] = x;
    return 1;
}

int Pop(Stack *s) {
    if (s->top == -1) {
        return 0;
    }
    return s->data[s->top--];
}

int GetTop(Stack *s) {
    if (s->top == -1) {
        return 0;
    }
    return s->data[s->top];
}

2. 定义一个运算符优先级表，用于比较运算符的优先级。

int priority(char op) {
    switch (op) {
        case '+':
        case '-':
            return 1;
        case '*':
        case '/':
            return 2;
        case '(':
            return 0;
    }
    return -1;
}

3. 读入表达式并进行求值。

int EvaluateExpression(char *exp) {
    Stack optr, opnd;
    InitStack(&optr);
    InitStack(&opnd);
    Push(&optr, '(');
    int i = 0;
    while (exp[i] != '\0') {
        if (exp[i] >= '0' && exp[i] <= '9') {
            int num = 0;
            while (exp[i] >= '0' && exp[i] <= '9') {
                num = num * 10 + exp[i] - '0';
                i++;
            }
            Push(&opnd, num);
        } else if (exp[i] == '+' || exp[i] == '-' || exp[i] == '*' || exp[i] == '/') {
            while (priority(exp[i]) <= priority(GetTop(&optr))) {
                int b = Pop(&opnd);
                int a = Pop(&opnd);
                char op = Pop(&optr);
                int result;
                switch (op) {
                    case '+':
                        result = a + b;
                        break;
                    case '-':
                        result = a - b;
                        break;
                    case '*':
                        result = a * b;
                        break;
                    case '/':
                        result = a / b;
                        break;
                }
                Push(&opnd, result);
            }
            Push(&optr, exp[i]);
            i++;
        } else if (exp[i] == '(') {
            Push(&optr, exp[i]);
            i++;
        } else if (exp[i] == ')') {
            while (GetTop(&optr) != '(') {
                int b = Pop(&opnd);
                int a = Pop(&opnd);
                char op = Pop(&optr);
                int result;
                switch (op) {
                    case '+':
                        result = a + b;
                        break;
                    case '-':
                        result = a - b;
                        break;
                    case '*':
                        result = a * b;
                        break;
                    case '/':
                        result = a / b;
                        break;
                }
                Push(&opnd, result);
            }
            Pop(&optr);
            i++;
        } else {
            i++;
        }
    }
    while (GetTop(&optr) != '(') {
        int b = Pop(&opnd);
        int a = Pop(&opnd);
        char op = Pop(&optr);
        int result;
        switch (op) {
            case '+':
                result = a + b;
                break;
            case '-':
                result = a - b;
                break;
            case '*':
                result = a * b;
                break;
            case '/':
                result = a / b;
                break;
        }
        Push(&opnd, result);
    }
    return GetTop(&opnd);
}

4. 调用函数进行表达式求值。

char exp[] = "3+4*5-(6*2+1)";
int result = EvaluateExpression(exp);
printf("%d\n", result); // 输出：10