Question

Как известно, существуют разные формы записи алгебраических выражений: инфиксная, префиксная и постфиксная (или обратная польская запись). Вычислите значение выражения, записанного в постфиксной записи: 3 4 6 * + 8 2 - * 2 3 4 5 * 6 + 7 + 8 4 2 * 3 4 9 + 3 4 + * 5 + + * + + * * *. В качестве ответа выведите одно целое число — значение выражения.

Answer 1

3 (4 6 *) + 8 2 - * 2 3 4 5 * 6 + 7 + 8 4 2 * 3 4 9 + 3 4 + * 5 + + * + + * * *
4*6=24
(3 24 +) 8 2 - * 2 3 4 5 * 6 + 7 + 8 4 2 * 3 4 9 + 3 4 + * 5 + + * + + * * *
3+24=27
13 (8 2 -) * 2 3 4 5 * 6 + 7 + 8 4 2 * 3 4 9 + 3 4 + * 5 + + * + + * * *
8-2=6
(27 6 *) 2 3 4 5 * 6 + 7 + 8 4 2 * 3 4 9 + 3 4 + * 5 + + * + + * * *
27*6=162
162 2 3 (4 5 *) 6 + 7 + 8 4 2 * 3 4 9 + 3 4 + * 5 + + * + + * * *
4*5=20
162 2 3 (20 6 +) 7 + 8 4 2 * 3 4 9 + 3 4 + * 5 + + * + + * * *
20+6=26
162 2 3 (26 7 +) 8 4 2 * 3 4 9 + 3 4 + * 5 + + * + + * * *
26+7=33
162 2 3 33 8 (4 2 *) 3 4 9 + 3 4 + * 5 + + * + + * * *
4*2=8
162 2 3 33 8 8 3 (4 9 +) 3 4 + * 5 + + * + + * * *
4+9=13
162 2 3 33 8 8 3 13 (3 4 +) * 5 + + * + + * * *
3+4=7
162 2 3 33 8 8 3 (13 7 *) 5 + + * + + * * *
13*7=91
162 2 3 33 8 8 3 (91 5 +) + * + + * * *
91+5=96
162 2 3 33 8 8 (3 96 +) * + + * * *
3+96=99
162 2 3 33 8 (8 99 *) + + * * *
8*99=792
162 2 3 33 (8 792 +) + * * *
792+8=800
162 2 3 (33 800 +) * * *
33+800=833
162 2 (3 833 *) * *
3*833=2499
162 (2 2499 *) *
2*2499=4998
162 4998 *
162*4998=809676

Эквивалентное выражение
(3+4*6)*(8-2)*2*3*(4*5+6+7+8+4*2*(3+(4+9)*(3+4)+5))

Ответ: 809676

Answer 2

Для вычисления значения выражения, записанного в постфиксной (обратной польской) записи, мы можем использовать стек. Идея заключается в том, что мы идем по выражению слева направо и выполняем операции над числами, когда встречаем их, или кладем числа в стек, когда встречаем их.

Давайте разберемся, как это работает на примере данного выражения:

3 4 6 * 8 2 - * 2 3 4 5 * 6 7 8 4 2 * 3 4 9 3 4 * * 5 * * * *

1. Мы идем по выражению слева направо, начиная с числа 3. Мы кладем его в стек.

Стек: [3]

2. Мы встречаем число 4. Мы кладем его в стек.

Стек: [3, 4]

3. Мы встречаем число 6. Мы кладем его в стек.

Стек: [3, 4, 6]

4. Мы встречаем операцию умножения (*). Мы достаем два последних числа из стека (6 и 4), выполняем операцию умножения и кладем результат (24) обратно в стек.

Стек: [3, 24]

5. Мы встречаем число 8. Мы кладем его в стек.

Стек: [3, 24, 8]

6. Мы встречаем число 2. Мы кладем его в стек.

Стек: [3, 24, 8, 2]

7. Мы встречаем операцию вычитания (-). Мы достаем два последних числа из стека (2 и 8), выполняем операцию вычитания и кладем результат (-6) обратно в стек.

Стек: [3, 24, -6]

8. Мы встречаем операцию умножения (*). Мы достаем два последних числа из стека (-6 и 24), выполняем операцию умножения и кладем результат (-144) обратно в стек.

Стек: [3, -144]

9. Мы встречаем число 2. Мы кладем его в стек.

Стек: [3, -144, 2]

10. Мы встречаем число 3. Мы кладем его в стек.

Стек: [3, -144, 2, 3]

11. Мы встречаем число 4. Мы кладем его в стек.

Стек: [3, -144, 2, 3, 4]

12. Мы встречаем операцию умножения (*). Мы достаем два последних числа из стека (4 и 3), выполняем операцию умножения и кладем результат (12) обратно в стек.

Стек: [3, -144, 2, 12]

13. Мы встречаем число 5. Мы кладем его в стек.

Стек: [3, -144, 2, 12, 5]

14. Мы встречаем операцию умножения (*). Мы достаем два последних числа из стека (5 и 12), выполняем операцию умножения и кладем результат (60) обратно в стек.

Стек: [3, -144, 2, 60]

15. Мы встречаем число 6. Мы кладем его в стек.

Стек: [3, -144, 2, 60, 6]

16. Мы встречаем число 7. Мы кладем его в стек.

Стек: [3, -144, 2, 60, 6, 7]

17. Мы встречаем число 8. Мы кладем его в стек.

Стек: [3, -144, 2, 60, 6, 7, 8]

18. Мы встречаем число 4. Мы кладем его в стек.

Стек: [3, -144, 2, 60, 6, 7, 8, 4]

19. Мы встречаем число 2. Мы кладем его в стек.

Стек: [3, -144, 2, 60, 6, 7, 8, 4, 2]

20. Мы встречаем операцию умножения (*). Мы достаем два последних числа из стека (2 и 4), выполняем операцию умножения и кладем результат (8) обратно в стек.

Стек: [3, -144, 2, 60, 6, 7, 8, 8]

21. Мы встречаем число 3. Мы кладем его в стек.

Стек: [3, -144, 2, 60, 6, 7, 8, 8, 3]

22. Мы встречаем число 4. Мы кладем его в стек.

Стек: [3, -144, 2, 60, 6, 7, 8, 8, 3, 4]

23. Мы встречаем число 9. Мы кладем его в стек.

Стек: [3, -144, 2, 60, 6, 7, 8, 8, 3, 4, 9]

24. Мы встречаем операцию умножения (*). Мы достаем два последних числа из стека (9 и 4), выполняем операцию умножения и кладем результат (36) обратно в стек.

Стек: [3, -144, 2, 60, 6, 7, 8, 8, 3, 36]

25. Мы встречаем число 3. Мы кладем его в стек.

Стек: [3, -144, 2, 60, 6, 7, 8, 8, 3, 36, 3]

26. Мы встречаем число 4. Мы кладем его в стек.

Стек: [3, -144, 2, 60, 6, 7, 8, 8, 3, 36, 3, 4]

27. Мы встречаем операцию умножения (*). Мы достаем два последних числа из стека (4 и 3), выполняем операцию умножения и кладем результат (12) обратно в стек.

Стек: [3, -144, 2, 60, 6, 7, 8, 8, 3, 36, 12]

28. Мы встречаем операцию умножения (*). Мы достаем два последних числа из стека (12 и 36), выполняем операцию умножения и кладем результат (432) обратно в стек.

Стек: [3, -144, 2, 60, 6, 7, 8, 8, 432]

29. Мы встречаем операцию умножения (*). Мы достаем два последних числа из стека (432 и 8), выполняем операцию умножения и кладем результат (3456) обратно в стек.

Стек: [3, -144, 2, 60, 6, 7, 3456]

30. Мы встречаем операцию умножения (*). Мы достаем два последних числа из стека (3456 и 7), выполняем операцию умножения и кладем результат (24192) обратно в стек.

Стек: [3, -144, 2, 60, 24192]