编译原理用c语言实现逆波兰式的生成和计算

下面是使用 C 语言实现逆波兰式的生成和计算的代码示例：

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

#define MAX_STACK_SIZE 100
#define MAX_EXPR_SIZE 100

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

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

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

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

void push(Stack *s, char *x) {
    if (is_full(s)) {
        printf("Stack overflow.\n");
        exit(1);
    }
    strcpy(s->data[++s->top], x);
}

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

int is_operator(char *op) {
    return (strcmp(op, "+") == 0 ||
            strcmp(op, "-") == 0 ||
            strcmp(op, "*") == 0 ||
            strcmp(op, "/") == 0);
}

int get_precedence(char *op) {
    if (strcmp(op, "+") == 0 || strcmp(op, "-") == 0) {
        return 1;
    } else if (strcmp(op, "*") == 0 || strcmp(op, "/") == 0) {
        return 2;
    } else {
        return 0;
    }
}

void infix_to_postfix(char *infix, char *postfix) {
    Stack op_stack;
    init_stack(&op_stack);

    char *p = infix;
    char *q = postfix;
    while (*p) {
        if (isdigit(*p)) {
            while (isdigit(*p)) {
                *q++ = *p++;
            }
            *q++ = ' ';
        } else if (is_operator(p)) {
            while (!is_empty(&op_stack) &&
                   get_precedence(p) <= get_precedence(op_stack.data[op_stack.top])) {
                strcat(q, pop(&op_stack));
                strcat(q, " ");
            }
            push(&op_stack, p);
            p++;
        } else if (*p == '(') {
            push(&op_stack, p);
            p++;
        } else if (*p == ')') {
            while (op_stack.data[op_stack.top][0] != '(') {
                strcat(q, pop(&op_stack));
                strcat(q, " ");
            }
            pop(&op_stack);
            p++;
        } else {
            p++;
        }
    }

    while (!is_empty(&op_stack)) {
        strcat(q, pop(&op_stack));
        strcat(q, " ");
    }
}

int evaluate_postfix(char *postfix) {
    Stack op_stack;
    init_stack(&op_stack);

    char *p = postfix;
    while (*p) {
        if (isdigit(*p)) {
            int num = 0;
            while (isdigit(*p)) {
                num = num * 10 + (*p - '0');
                p++;
            }
            push(&op_stack, num);
        } else if (is_operator(p)) {
            int a = atoi(pop(&op_stack));
            int b = atoi(pop(&op_stack));
            int result;
            if (strcmp(p, "+") == 0) {
                result = b + a;
            } else if (strcmp(p, "-") == 0) {
                result = b - a;
            } else if (strcmp(p, "*") == 0) {
                result = b * a;
            } else if (strcmp(p, "/") == 0) {
                result = b / a;
            }
            char temp[MAX_EXPR_SIZE];
            sprintf(temp, "%d", result);
            push(&op_stack, temp);
            p++;
        } else {
            p++;
        }
    }

    return atoi(pop(&op_stack));
}

int main() {
    char infix_expr[MAX_EXPR_SIZE];
    printf("Enter an infix expression: ");
    scanf("%[^\n]%*c", infix_expr);

    char postfix_expr[MAX_EXPR_SIZE];
    infix_to_postfix(infix_expr, postfix_expr);
    printf("Postfix expression: %s\n", postfix_expr);

    int result = evaluate_postfix(postfix_expr);
    printf("Result: %d\n", result);

    return 0;
}

这段代码中，我们首先实现了将中缀表达式转换为后缀表达式的函数 `infix_to_postfix`，然后实现了利用后缀表达式进行计算的函数 `evaluate_postfix`。在中缀转后缀的过程中，我们使用了栈来存储运算符，并在遍历完整个表达式后将栈中剩余的运算符弹出并添加到后缀表达式中。在计算后缀表达式的过程中，我们同样使用了栈来存储数字，并在遍历完整个表达式后将栈中剩余的数字弹出并进行运算。