基于链表实现栈的C++中缀转后缀程序运行时错误求助

Let's fix your infix-to-postfix converter step by step—your code has several logical bugs that are causing the runtime crash, especially with simple inputs like a+b.

Key Issues in Your Code #

• Broken Pre Function: Right now, your Pre function incorrectly checks if the stack is empty (top==NULL) as part of its priority calculation. This function should only return the priority of the input character, not check stack state. Also, it doesn't handle operands (like a, b) correctly—right now it returns 3 for non-operators, which is wrong because operands should be directly added to the postfix output, not pushed to the stack.
• No Check for Operands: Your InToPost function treats every character as an operator. When you input a, it tries to compare its priority with the stack top (which is NULL initially), leading to a null pointer dereference crash.
• Incorrect Operator Handling Logic: When the current operator has lower or equal priority than the stack top, you pop elements to postfix but never push the current operator to the stack, and you don't increment i—this leads to infinite loops or unprocessed characters.
• Unsafe Stack Access: You access top->data without checking if top is NULL first. When the stack is empty (like at the start of conversion), this causes a runtime crash.
• Mismatched Return Type in Pop: You initialize x as an int with -1, but return a char. While this works in some cases, using a char default (like '\0') is cleaner and avoids confusion.

Fixed Code #

#include <iostream>
#include <cstring>
using namespace std;

struct Node {
    char data;
    struct Node* next;
}* top = NULL;

void Push(char x) {
    struct Node* p = new Node;
    if (p == NULL)
        cout << "\nStack Overflow";
    else {
        p->data = x;
        p->next = top;
        top = p;
    }
}

char Pop() {
    // Use char default instead of int to match return type
    char x = '\0';
    struct Node* p;
    if (top == NULL)
        cout << "\nStack is Empty";
    else {
        p = top;
        x = p->data;
        top = top->next;
        delete p;
    }
    return x;
}

int isEmpty() {
    return top ? 0 : 1;
}

// Fixed Pre function: returns priority of the input character only
int Pre(char ch) {
    if (ch == '+' || ch == '-')
        return 1;
    else if (ch == '*' || ch == '/')
        return 2;
    // Return 0 for operands (non-operator characters)
    else
        return 0;
}

char* InToPost(char* infix) {
    char* postfix = new char[strlen(infix) + 1];
    int i = 0, j = 0;

    while (infix[i] != '\0') {
        // Directly add operands to postfix string
        if (Pre(infix[i]) == 0) {
            postfix[j++] = infix[i++];
        } else {
            // Handle operators safely: check if stack is empty first
            if (isEmpty() || Pre(infix[i]) > Pre(top->data)) {
                Push(infix[i++]);
            } else {
                // Pop all operators with >= priority than current
                while (!isEmpty() && Pre(infix[i]) <= Pre(top->data)) {
                    postfix[j++] = Pop();
                }
                // Push the current operator after popping
                Push(infix[i++]);
            }
        }
    }
    // Pop remaining operators from stack to postfix
    while (!isEmpty()) {
        postfix[j++] = Pop();
    }
    postfix[j] = '\0';
    return postfix;
}

int main() {
    char* infix = new char[30];
    cin >> infix;
    char* postfix = InToPost(infix);
    cout << postfix << endl;
    // Clean up allocated memory to avoid leaks
    delete[] infix;
    delete[] postfix;
    return 0;
}

What Changed: #

1. Fixed Pre Function: Now it returns 0 for operands, 1 for +/-, and 2 for *//—no more checking stack state here.
2. Operand Handling: Added a check to directly add operands to the postfix string instead of treating them as operators.
3. Safe Stack Access: We now check if the stack is empty before accessing top->data, preventing null pointer crashes.
4. Correct Operator Logic: After popping higher/equal priority operators, we push the current operator to the stack and increment i to avoid infinite loops.
5. Memory Cleanup: Added delete[] calls for allocated arrays to prevent memory leaks.
6. Consistent Return Type: Updated Pop to use a char default value matching its return type.

内容的提问来源于stack exchange，提问作者Shashank Mishra