验证 PN 表达式

Question

如何检查PN表达式是否正确？

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

struct sNode {
    char data;
    struct sNode *next;
};

void push(struct sNode** top_ref, int new_data) {
    printf("Insert to stack %d\n", new_data);
    struct sNode* new_node = (struct sNode*) malloc(sizeof(struct sNode));

    if(new_node == NULL) {
        printf("Stack overflow \n");
        getchar();
        exit(0);
    }

    new_node->data = new_data;
    new_node->next = (*top_ref);
    (*top_ref) = new_node;
}

int pop(struct sNode** top_ref) {
    char res;
    struct sNode *top;

    if(*top_ref == NULL) {
        printf("Stack overflow \n");
        getchar();
        exit(0);
    } else {
        top = *top_ref;
        res = top->data;
        *top_ref = top->next;
        free(top);
        printf("Remove from stack %d\n",res);
        return res;
    }
}

void evaluate_rpm() {
    char c;
    struct sNode *stack = NULL;
    char number[10] = "";
    number[9] = 0;
    int i = 0, val1, val2;

    do {
        c = (char) getchar();
        if (c >= '0' && c <= '9') {
            number[i++] = c;
        } else if (c == '*') {
            val1 = pop(&stack);
            val2 = pop(&stack);
            push(&stack, val1 * val2);
        } else if (c == '/') {
            val1 = pop(&stack);
            val2 = pop(&stack);
            if (val1 == 0) {
                fprintf(stderr, "[!] Illegal divide by zero. Exiting...\n");
                exit(0);
            }
            push(&stack, val2 / val1);
        } else if (c == '-') {
            val1 = pop(&stack);
            val2 = pop(&stack);
            push(&stack, val2 - val1);
        } else if (c == '+') {
            val1 = pop(&stack);
            val2 = pop(&stack);
            push(&stack, val1 + val2);
        } else if (c == ' ' && i != 0) {
            val1 = atoi(number);
            push(&stack, val1);
            int j;
            for (j = 0; j <= i; j++) {
                number[j] = 0;
            }
            i = 0;
        } else if (c == '\n') {
            val1 = pop(&stack);
            printf("=========================\n");
            printf("result of evaluation %d\n", val1);
            printf("=========================\n");
        } else if (c != ' ' && c != EOF) {
            printf("%d\n", (int)c);
            fprintf(stderr, "[!] Syntax error in input. Exiting...\n");
            exit(1);
        }
    } while (c != EOF);
}

int main() {
    printf("Enter an expression.\n");
    evaluate_rpm();
    return 0;
}

Answer 1

如果出现堆栈下溢，或者最终堆栈中有多个项目，则会出现错误。

但是PN或RPN中没有括号。

验证 PN 表达式

Validate PN expression

c

stack

rpn