c++ - Infix to Postfix to Output (Postfix Calculator) 使用堆栈

Question

大家好!我是 C++ 的新手(这里也是 stackoverflow 的新手)，我需要各位专家的帮助。

我这里有一个代码，它应该向用户询问中缀表达式，然后将其转换为后缀并输出结果(后缀计算器)。但是，我无法立即将后缀转换为输出，因此一旦它显示后缀表达式，它就会在输出真正的答案之前再次请求后缀表达式(例如 1 2 + 之后有空格)。

没有错误或警告，但是当我运行程序时，计算机在显示后缀表达式后说“file.exe 已停止工作”。所以程序能够正确地将中缀表达式转换为后缀表达式，但在显示输出时仍然存在一些错误。

#include <iostream>
#include <cstring>
#include <cstdlib>

using namespace std;

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

node *top=NULL;
node *bottom=NULL;
node *key;
node *last;
node *before_last;


void push (const char Symbol) {
    key = new node;
    key->data = Symbol;
    key->next = top;
    top = key;
}

void push_for_output (node* &stack, int key) {
    node* newNode = new node;
    newNode->data = key;
    newNode->next = stack;
    stack = newNode;
}

const char pop() {
    if (!top) {
        cout << "Stack underflow\n" << endl;
        return ' ';
    }
    node* key = top;
    top = top->next;
    char ch = key->data;
    delete key;
    return ch;
}

int pop_for_output (node* &stack) {
    int key = stack->data;
    node* nodeToDelete = stack;
    stack = stack->next;
    delete nodeToDelete;
    return key;
}

bool isOperator (char *token) {
    if (strcmp(token, "+") == 0) {
        return true;
    }
    else if (strcmp(token, "-") == 0) {
        return true;
    }
    else if (strcmp(token, "*") == 0) {
        return true;
    }
    else if (strcmp(token, "/") == 0) {
        return true;
    }
    else {
        return false;
    }
}



const bool is_empty() {
    return !top;
}

int postfix(const char *infix) {
    char infix_ch[100]={NULL};
    char postfix_ch[100]={NULL};
    node* stack = NULL;

    strcpy(infix_ch,"(");
    strcat(infix_ch, infix);
    strcat(infix_ch,")");

    char symbol[5]={NULL};
    char temp[5]={NULL};

    for(int i=0; i<strlen(infix_ch); i++) {
        symbol[0]=infix_ch[i];

        if(symbol[0]=='(')
            push(symbol[0]);

        else if(symbol[0]==')') {
            symbol[0]=pop( );
            while(symbol[0]!='(') {
                strcat(postfix_ch, symbol);
                symbol[0]=pop( );
            }
        }

         else if(symbol[0]=='^' || symbol[0]=='*' || symbol[0]=='/' || symbol[0]=='+' || symbol[0]=='-') {
            if(symbol[0]=='*' || symbol[0]=='/') {
                temp[0]=pop( );
                while(temp[0]=='^' || temp[0]=='*' || temp[0]=='/') {
                   strcat(postfix_ch, temp);
                   temp[0]=pop( );
                }
                push(temp[0]);
            }

            else if(symbol[0]=='+' || symbol[0]=='-') {
                temp[0]=pop( );
                while(temp[0]!='(') {
                    strcat(postfix_ch, temp);
                    temp[0]=pop( );
                }
                push(temp[0]);
            }
            push(symbol[0]);
        }

            else
                strcat(postfix_ch, symbol);
    }

       cout << "Postfix: " << postfix_ch;

       char postfix[80];
        cout << "\nEnter postfix expression (include spaces between each operand and/or operator): ";
       cin.getline(postfix, 80);
       char *tokens = strtok(postfix, " ");
       while (tokens != NULL) {
        if (isOperator (tokens)) {
            int operand2 = pop_for_output(stack);
            int operand1 = pop_for_output(stack);
            int result;

            if (strcmp(tokens, "+") == 0) {
                result = operand1 + operand2;
            }
            else if (strcmp(tokens, "-") == 0) {
                result = operand1 - operand2;
            }
            else if (strcmp(tokens, "*") == 0) {
                result = operand1 * operand2;
            }
            else if (strcmp(tokens, "/") == 0) {
                result = operand1 / operand2;
            }

            push_for_output (stack, result);
        }
        else {
            push_for_output (stack, atoi (tokens));
        }
        tokens = strtok(NULL, " ");
    }
    cout << pop_for_output(stack);
    system("pause");
    return 0;
}


 int main( ) {
    char infix_values[100]={NULL};
    cout << "Enter the infix equation: ";
    cin >> infix_values;
    postfix(infix_values);
}

我是新手，我真的需要各位专家的帮助。如果你帮我改正我的程序，我将不胜感激。非常感谢，祝您有愉快的一天!

Answer 1

一个可能的问题是 pop_for_output() 函数永远不会像您在 pop() 中那样检查空/NULL 堆栈。如果输入了无效的后缀表达式，或者如果您的解析不正确，您很容易陷入引用 NULL 指针的情况，这可以很好地解释崩溃。