递归Push-Pop后缀计算器无法正确运算，仅返回最后输入数字

Let’s walk through why your calculator is only returning the last input number, and how to fix it while respecting all your constraints (pop() returns a boolean, stack uses a char array, single string input).

Common Root Causes #

First, let’s diagnose the likely issues tripping you up:

• Incorrect token handling: If you’re processing each character individually instead of grouping multi-digit numbers, your stack will end up with single digits instead of full values—leading to no actual calculations, just the last digit being returned.
• Flawed recursive logic: You’re probably not properly popping two operands when hitting an operator, computing the result, and pushing it back. Instead, you’re just pushing numbers and skipping the critical operation step.
• Stack operation order: Since pop() doesn’t return a value, you need to carefully sequence peek() and pop() to get your operands in the right order for postfix evaluation.

Step-by-Step Solution #

1. First: Tokenize the Input String

You can’t process each character as a standalone token. You need to group digits into full numbers and separate them from operators. For example, "123 45 +" should become tokens 123, 45, +.

Here’s a simple way to do this (pseudocode):

function tokenize(input):
    tokens = empty list
    currentNumber = ""
    for each char c in input:
        if c is whitespace:
            if currentNumber is not empty:
                add currentNumber to tokens
                currentNumber = ""
        elif c is a digit:
            currentNumber += c
        else: # operator (+, -, *, /)
            if currentNumber is not empty:
                add currentNumber to tokens
                currentNumber = ""
            add c to tokens
    # Add the last number if any is left
    if currentNumber is not empty:
        add currentNumber to tokens
    return tokens

2. Recursive Evaluation Logic

Your recursive function needs to process tokens in order, manipulate the stack correctly, and terminate when all tokens are processed. Remember: postfix expressions require popping two operands when you hit an operator, computing the result, and pushing it back.

Since pop() only returns a boolean, here’s the correct sequence for handling operators:

1. Verify the stack has at least two elements (throw an error if not—invalid expression).
2. Get the right operand: Use peek() to grab its value, then call pop() to remove it from the stack.
3. Get the left operand: Again, peek() first, then pop() to remove it.
4. Compute the result using the operator (critical note: left operand comes first for subtraction/division—a b - means a - b, not b - a).
5. Push the result back to the stack.
6. Recurse to process the next token.

Here’s what the recursive function might look like (pseudocode, assuming a stack class with push(int), pop() -> boolean, peek() -> int, size() -> int):

function evaluate(tokens, index):
    # Termination condition: all tokens processed
    if index >= tokens.length:
        return stack.peek()
    
    currentToken = tokens[index]
    if currentToken is a number:
        stack.push(parseInt(currentToken))
        return evaluate(tokens, index + 1)
    else: # operator
        # Check stack has enough operands
        if stack.size() < 2:
            throw error("Invalid postfix expression: not enough operands")
        
        # Get right operand
        int right = stack.peek()
        if not stack.pop():
            throw error("Failed to pop right operand")
        
        # Get left operand
        int left = stack.peek()
        if not stack.pop():
            throw error("Failed to pop left operand")
        
        # Compute result
        int result = 0
        switch currentToken:
            case '+': result = left + right
            case '-': result = left - right
            case '*': result = left * right
            case '/': 
                if right == 0:
                    throw error("Division by zero")
                result = left / right
            default:
                throw error("Invalid operator: " + currentToken)
        
        stack.push(result)
        return evaluate(tokens, index + 1)

3. Tie It All Together

Your main program flow should:

• Prompt the user: Please enter expression:
• Read the input string
• Tokenize it using the function above
• Initialize your char-array-backed stack
• Call the recursive evaluate function starting at index 0
• Print the final stack peek value

Example Test Run #

If input is "3 4 +":

1. Tokenize to ["3", "4", "+"]
2. Recurse index 0: push 3, move to index 1
3. Recurse index 1: push 4, move to index 2
4. Recurse index 2: handle '+', pop 4 (right), pop 3 (left), compute 3+4=7, push 7, move to index 3
5. Terminate, return stack.peek() = 7

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