c - 如何在堆栈中进行 RPN 计算？

Question

我试图解决的一本 C 编程书中的问题是这个，我很难理解，尤其是 pop() 函数在这种情况下是如何工作的:

For example, 1 + 2 would be written 1 2 + in RPN, and 1 + 2 * 3 would be written 1 2 3 * +. RPN expressions can easily be evaluated using a stack. The algorithm involves reading the operators and operands in an expression from left to right, performing the following actions:

When an operand is encountered, push it onto the stack.

When an operator is encountered, pop its operands from the stack, perform the operation on those operands and then push the result onto the stack.

Write a program that evaluates RPN expressions. The operands will be single-digit integers, The operators are +, -, *, /, and =. The = operator causes the top stack item to be displayed; afterwards, the stack is cleared and the user is prompted to enter another expression. The process continues until the user enters a character that is not an operator or operand:

Enter an RPN expression: 1 2 3 * + =

Value of expression: 7

Enter an RPN expression: 5 8 * 4 9 - / =

Value of expression: -8

Enter an RPN expression: q

If the stack overflows, the program will display the message Expression is too complex and terminate. If the stack underflows (because of an expression such as 1 2 + +), the program will display the message Not enough operands in expression and terminate. Hints: Incorporate the stack code from Section 10.2 into your program. Use scanf(" %c", &ch) to read the operators and operands.

case '+':   push(pop() + pop());
                    break;

case '-':   operand2 = pop();
            operand1 = pop();
            push(operand1 - operand2);
            break;

case '*':   push(pop() * pop());
            break;

case '/':   operand2 = pop();
            operand1 = pop();
            push(operand1 / operand2);
            break;

这些是我无法理解 pop() 如何知道要选择哪个数字的示例。

Answer 1

These are examples i can't understand how pop() knows which number to chose.

堆栈有一个用于存储项目的区域和一个用于跟踪当前“堆栈顶部”的变量。例如:

int myStack[1000];        // Area to store items
int myStackTop = 1000;    // Current "top of stack"

对于弹出它可能看起来像:

int pop(void) {
    int value = 0;

    if(myStackTop > 1000) {
        // Stack is empty, can't pop!
    } else {
        value = myStack[myStackTop];
        myStackTop++;
    }
    return value;
}

对于插入它可能是这样的:

void pop(int value) {

    if(myStackTop <= 0) {
        // Stack is full, can't push!
    } else {
        myStackTop--;
        myStack[myStackTop] = value;
    }
}

大部分；这是“当前堆栈顶部”变量，用于跟踪将选择哪个数字。