инфикс в постфикс с некоммутирующими операторами

У меня есть вопрос, когда речь заходит об операторах / в постфиксе и инфиксе.

Из задания

Входная строка 5 4 + 3 10 * + эквивалентна инфиксному выражению (5 + 4) + (3 * 10). Ответ — 39.

Я следую этому. Тогда меня смущает это утверждение.

Мы также должны побеспокоиться о некоммутирующих операторах — и / . Мы будем оценивать постфиксную строку 4 5 – как 4 – 5 и, аналогично, будем оценивать 4 5 / как 4 / 5 .

Однако, когда я это делаю... я получаю разные результаты с инфиксом и постфиксом.

Изменение первого примера для включения вычитания.

инфикс

(5 - 4) + (3 * 10) = 31

постфикс

5 4 - 3 10 * +

29....верно?

ТАК Я смущен. Результаты инфикса и постфикса должны быть одинаковыми, верно? Это опечатка в самом задании или я что-то не так делаю?


operators infix-notation postfix
person Jason    schedule 11.02.2018    source источник
comment
Как ты получил 29? Это помогло бы нам понять, откуда берется ошибка.   -  person Barry    schedule 12.02.2018

Ответы (4)


arrow_upward
0
arrow_downward

Когда вы оцениваете постфикс, вы используете стек: вы помещаете операнды, а когда вы добираетесь до оператора, вы выталкиваете требуемые операнды и помещаете оцененный результат.

В случае коммутативных операторов, таких как +, не имеет значения, в каком порядке находятся операнды. Так, например:

5 4 +

можно оценить как

PUSH 5
PUSH 4
PUSH (POP + POP)

где первый POP даст 4, а второй POP 5. Итак, вы действительно оценили 4+5.

Но в случае некоммутативных операторов это не сработает. Вы должны оценивать 5/4, а не 4/5. Поэтому вам нужно либо использовать временные переменные:

 PUSH 5
 PUSH 4
 let d = POP; // divisor = 4
 let q = POP; // quotient = 5
 PUSH q/d;    // push the dividend

или же ввести операцию SWAP, которая меняет местами два верхних элемента в стеке:

PUSH 5
PUSH 4
SWAP
PUSH (POP / POP)

или же скомпилировать постфикс, чтобы нажать в обратном порядке:

PUSH 4
PUSH 5
PUSH (POP/POP)
person user207421    schedule 11.02.2018
comment
Спасибо! Это работает. Меня смутила формулировка задания. Обмен или что-то в этом роде действительно то, что мне нужно. Я люблю этот материал. Без сарказма. - person Jason; 12.02.2018

arrow_upward
1
arrow_downward

Постфикс также принимает значение 31.

Давайте рассмотрим это шаг за шагом: Наше выражение

5 4 - 3 10 * +

Таким образом, стек прогрессирует следующим образом:

5
5 4
1      # after evaluating -, i.e. popping 5 and 4 and pushing 5 - 4
1 3
1 3 10
1 30   # after evaluating *, i.e. popping 3 and 10 and pushing 3 * 10
31     # after evaluating +, i.e. popping 1 and 30 and pushing 1 + 30
person Wintermute    schedule 11.02.2018
comment
Задание обрабатывает это по-разному. При обработке запасов он следовал модели «первым пришел — первым вышел». - person Jason; 12.02.2018
comment
Я полностью следую твоему примеру. Вы следовали LIFO... Я полностью понимаю, как это работает. Задание сделало наоборот. Он следовал FIFO... и выдавал мне ошибки при вычитании, потому что 5-4 в инфиксе становится 4-5 в постфиксе. - person Jason; 12.02.2018
comment
Но в задании указано, что 4 5 - должно оцениваться как 4 - 5, поэтому 5 4 - должно оцениваться как 5 - 4. Я не думаю, что это имеет какое-то отношение к порядку, в котором применяются операции, это просто вопрос того, какой операнд вы помещаете на какую сторону -. - person Wintermute; 12.02.2018
comment
Я также не совсем уверен, что такое стратегия FIFO для оценки RPN; Я только когда-либо видел, как это делается со стеком. Google мало что делает, чтобы просветить меня там. ›.‹ - person Wintermute; 12.02.2018

arrow_upward
1
arrow_downward

Я думаю, вы могли быть сбиты с толку, потому что пример 4-5, а ваш пример 5-4 для инфиксной записи.

Для оценки постфикса 5 4 - 3 10 * +:
5 4 - = 5 - 4 = 1
3 10 * = 3 * 10 = 30
1 30 + = 1 + 30 = 31
>

Второе утверждение из вашего задания просто уточняет, что если у вас есть что-то вроде 4 5 -, то это будет 4 - 5, а не 5 - 4.

person Justin T.    schedule 11.02.2018

arrow_upward
0
arrow_downward

В утверждении о - и /, это 4 5 -. Это -1, то есть 4-5.

В более длинном выражении: 5 4 - 3 10 * +

Это 5-4, потому что 5 идет первым. Таким образом, равно (5-4) + (3*10) = 31.

Если бы это было 4 5 - 3 10 * +, то это было бы равно 29 (т.е. (4-5) + (3*10)). Это связано не с префиксной или постфиксной нотацией, а с порядком, в котором мы оцениваем аргументы, потому что - и / не коммутативны. Присваивание указывает, что они будут оцениваться в «интуитивном» порядке, т. е. что x y - означает x - y.

person Umer Amjad    schedule 11.02.2018