如何用c语言代码实现中缀表达式求值

以下是一个简单的中缀表达式求值的实现。

步骤：

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

2. 从左到右扫描中缀表达式的每个元素。

3. 如果当前元素是数字，则将其压入栈中。

4. 如果当前元素是运算符，则将其与栈顶元素进行比较。

5. 如果栈顶元素是运算符且优先级高于当前运算符，则弹出栈顶元素并进行计算，计算结果压入栈中，再比较当前元素和新的栈顶元素。

6. 如果栈顶元素是左括号，则直接将当前元素压入栈中。

7. 如果当前元素是右括号，则弹出栈中元素，直到遇到左括号为止，将所有弹出的元素进行计算，结果压入栈中。

8. 扫描完整个表达式后，将栈中剩余的元素进行计算，最后栈中只剩下一个元素，即为表达式的值。

代码：

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

#define MAX_SIZE 100

typedef enum {
    false = 0, true
} bool;

typedef struct {
    int top;
    char data[MAX_SIZE];
} Stack;

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

bool isFull(Stack *s) {
    return s->top == MAX_SIZE - 1;
}

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

void push(Stack *s, char c) {
    if (isFull(s)) {
        printf("Stack overflow!\n");
        exit(EXIT_FAILURE);
    }
    s->data[++s->top] = c;
}

char pop(Stack *s) {
    if (isEmpty(s)) {
        printf("Stack underflow!\n");
        exit(EXIT_FAILURE);
    }
    return s->data[s->top--];
}

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

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

void infixToPostfix(char *infix, char *postfix) {
    Stack s;
    initStack(&s);

    int i = 0, j = 0;
    while (infix[i] != '\0') {
        char c = infix[i];
        if (isdigit(c)) {
            postfix[j++] = c;
        } else if (c == '(') {
            push(&s, c);
        } else if (c == ')') {
            while (peek(&s) != '(') {
                postfix[j++] = pop(&s);
            }
            pop(&s);
        } else {
            while (!isEmpty(&s) && peek(&s) != '(' && precedence(c) <= precedence(peek(&s))) {
                postfix[j++] = pop(&s);
            }
            push(&s, c);
        }
        i++;
    }

    while (!isEmpty(&s)) {
        postfix[j++] = pop(&s);
    }
    postfix[j] = '\0';
}

int evaluatePostfix(char *postfix) {
    Stack s;
    initStack(&s);

    int i = 0;
    while (postfix[i] != '\0') {
        char c = postfix[i];
        if (isdigit(c)) {
            push(&s, c - '0');
        } else {
            int x = pop(&s);
            int y = pop(&s);
            switch (c) {
                case '+':
                    push(&s, y + x);
                    break;
                case '-':
                    push(&s, y - x);
                    break;
                case '*':
                    push(&s, y * x);
                    break;
                case '/':
                    push(&s, y / x);
                    break;
                case '^':
                    push(&s, y ^ x);
                    break;
                default:
                    printf("Invalid operator!\n");
                    exit(EXIT_FAILURE);
            }
        }
        i++;
    }

    return pop(&s);
}

int evaluateInfix(char *infix) {
    char postfix[MAX_SIZE];
    infixToPostfix(infix, postfix);
    return evaluatePostfix(postfix);
}

int main() {
    char infix[MAX_SIZE];
    printf("Enter an infix expression: ");
    scanf("%s", infix);
    printf("Result: %d\n", evaluateInfix(infix));
    return 0;
}