Обратная польская нотация (ОПН) – использующаяся в некоторых языках программирования форма записи
математических выражений, в которой операнды расположены перед знаками операций.
Запись и вычисление выражения в ОПН устроены следующим образом:
- Выражение является последовательностью операндов и знаков операций.
- Выражение читается слева направо.
- Если в выражении встречается операнд, он заносится в стек операндов.
- Если в выражении встречается знак операции, выполняется соответствующая операция над двумя последними
операндами в стеке и эти два операнда заменяются на результат вычисления операции.
- Результатом вычисления выражения становится результат последней вычисленной операции.
Пример вычисления выражения: 7 2 3 + - 4 *
| Шаг |
Текущее выражение |
Стек операндов |
| 1 |
7 2 3 + - 4 * |
7 |
| 2 |
2 3 + - 4 * |
7 2 |
| 3 |
3 + - 4 * |
7 2 3 |
| 4 |
+ - 4 * |
7 5 |
| 5 |
- 4 * |
2 |
| 6 |
4 * |
2 4 |
| 7 |
* |
8 |
Дано выражение, записанное в ОПН:
2 4 4 #1 #2 8 1 #1 #3
За символами “#1”, “#2” и “#3” скрываются операции сложения, вычитания и умножения (в выражении присутствую все три операции), но неизвестно, какая операция соответствует какому символу. Подберите такой вариант соответствия символов операциям, при котором значение вычисленного выражения будет максимальным, и вычислите это значение. В ответе укажите целое число.