Перевод из постфиксной в инфиксную нотацию

Постфиксная нотация – это запись выражения по следующему правилу: сначала перечисляются аргументы оператора, а затем сам оператор. Например, выражение “a–(b+c)*c” запишется как “(a ((b c +) c *) –)”. Конечно, это выглядит несколько непривычно. Но заметим, что эта нотация одна из самых привычных нотаций для компьютера. Выражения, записанные в таком виде легко разобрать алгоритмически и вычислить. Одно из интересных наблюдений заключается в том, что нет необходимости использовать скобки. В частности, если в выражении “(a ((b c +) c *) –)” удалить все скобки, то получится выражение “a b c + c * –”, которое по-прежнему интерпретируется однозначно. В данной статье мы подробно рассмотрим постфиксную нотацию и научимся вычислять выражения, записанные этой нотации, а также сформулируем исследовательскую задачу о минимизации числа скобок в выражении, записанном в привычном нам виде (в инфиксной нотации).