Как я могу сделать расчет RPN в стеке?

Question

Вопрос из C книги по программированию, которую я пытаюсь решить, заключается в следующем, и мне трудно понять, особенно, как работает функция pop () в этом случае:

Например, 1 + 2 будет написано 1 2 + в RPN, а 1 + 2 * 3 будет записано 1 2 3 * +. Выражения RPN можно легко оценить с помощью стека. Алгоритм включает чтение операторов и операндов в выражении слева направо, выполняя следующие действия:

При обнаружении операнда положить его в стек sh.

Когда Обнаружен оператор, извлекает его операнды из стека, выполняет операцию с этими операндами и затем выводит sh результат в стек.

Напишите программу, которая оценивает выражения RPN. Операнды будут целыми числами с одинарным ди git, операторы +, -, *, / и =. Оператор = заставляет отображаться верхний элемент стека; после этого стек очищается, и пользователю предлагается ввести другое выражение. Процесс продолжается до тех пор, пока пользователь не введет символ, который не является оператором или операндом:

Введите выражение RPN: 1 2 3 * + =

Значение выражения: 7

Введите выражение RPN: 5 8 * 4 9 - / =

Значение выражения: -8

Введите выражение RPN: q

Если стек переполняется, Программа отобразит сообщение Выражение слишком сложное и прекратит работу. Если стек переполнен (из-за выражения, такого как 1 2 + +), программа отобразит сообщение «Недостаточно операндов в выражении» и завершится. Подсказки: включите код стека из Раздела 10.2 в вашу программу. Используйте scanf ("% c", & ch) для чтения операторов и операндов.

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

Это примеры, которые я не могу понять, как pop () знает, какое число выбрать.

В стеке есть область для хранения элементов и переменная для отслеживания текущего "вершина стека". Например:

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;
    }
}

Преимущественно; именно эта переменная "top of of stack" отслеживает, какое число будет выбрано.