Читаем Программирование на языке Ruby полностью

При выполнении любой арифметической операции число элементов в стеке уменьшается на 1. Попытки выполнить операцию, когда в стеке меньше двух элементов, или показать результат, когда стек пуст, приводят к отказу.

Рассмотрим пример для стекового калькулятора. Пусть требуется получить значение формулы 5 - (7+8) +25. Тогда последовательность для стекового калькулятора будет такой: 5,7,8, +, •, 25, +.

Из предыдущего примера видно, что обычная формула преобразуется в некую последовательность для стекового калькулятора. Причем эта последовательность преобразуем мы сами. Наша же задача написать программу, которая делает это для любой формулы автоматически. Такая программа называется компилятором с языка арифметических формул на язык понятный стековому калькулятору.

4.1 Рекурсивная реализация компилятора правильных формул.

Будем для определенности считать, что язык правильных формул задается грамматикой:

формула→терм | терм+формула | терм-формула

терм→множитель | множитель • терм | множитель / терм

множитель→(формула) | переменная

переменная→a\b\…\z и рассмотрим реализацию компилятора в соответствии с этой грамматикой.

Правильная формула задается грамматикой с четырьмя метасимволами. Для каждого метасимвола пишется отдельный метод обработки. Например, метод «обработать терм» находит в начале непрочитанной части формулы терм максимальной длины, читает и печатает соответствующий фрагмент последовательности для стекового калькулятора.

В используемой нами грамматике понятие терм определяется через понятия терм и формула. Естественно поэтому попытаться реализовать обработку формулы рекурсивно. (Напомним, что рекурсия – это ситуация или программистский прием, состоящий в том, что программа непосредственно или через другие программы обращается к себе как к подпрограмме.)

В соответствии с определением формулы при ее компиляции можно сначала найти и откомпилировать терм: либо этот терм совпадает со всей формулой, либо за ним должен следовать знак + или —. Таким образом, после компиляции терма возможны три ситуации:

• в формуле больше символов нет;

• далее идет знак +, а за ним формула;

• далее идет знак —, а за ним формула.

Соответственно в целом обработку формулы можно записать так: обрабатывается терм, затем проводится выбор: если нет непрочитанных элементов, то ничего не делать; если идет знак + или —, то пропустить его, обработать формулу и напечатать соответственно + или —.

Обратите внимание, что в методе «обработать формулу» мы обрабатываем непрочитанную часть формулы не до ее конца, а лишь до конца правильной формулы. Это связанно с тем, что далее при обработке множителя в соответствии с правилом:

множитель→(формула) \ переменная мы будем вызывать метод «обработать формулу» для компиляции выражения внутри скобок, а такая обработка должна заканчиваться при достижении закрывающейся скобки.

Наконец, коль скоро мы воспользовались рекурсией, мы обязаны гарантировать, что метод «обработать формулу» не будет вызывать себя бесконечно. В данном случае это действительно так, потому что перед каждым новым вызовом метода «обработать формулу» непрочитанная часть формулы уменьшается, а т.к. она конечна, то и вызовов может быть лишь конечное число. Следовательно, рано или поздно обработка формулы закончится.

Рекурсивный компилятор формул (RecursCompf.rb)

class RecursComp def compile(str)

     @str,@index = str,0

     compileF

end

private

def compileF

compileT

     return if @index >= @str.length

     cur = @str[@index].chr

     if cur == ’+’ or cur ==

          @index += 1

          compileF

          print "#{cur} "

     end

end

def compileT

     compileM

     return if @index >= @str.length

     cur = @str[@index].chr if cur == ’*’ or cur == ’/’

     @index += 1

     compileT

     print "#{cur} "

     end

end

     def compileM

if @str[@index].chr == ’(’ @index += 1

     compileF

     @index += 1

else

     compileV

     end

end

def compileV

     print "#{@str[@index].chr} "

     @index += 1

     end

end

Аналогичным способом в соответствии с грамматикой реализуются методы «обработать терм», «обработать множитель». А метод «обработать переменную» заключается лишь в выводе на экран переменной и пропуске очередного элемента.

Однако, если попытаться откомпилировать нашим компилятором формулу а – b — с, то мы увидим, что последовательность символов для стекового калькулятора соответствует формуле а – (b — с), т.е. в этой ситуации компилятор работает неверно (традиционная операция вычитания ассоциативна слева, а у нас скобки «накапливаются» справа)[12].

Обработка ввода формул (RecursComp.rb)

require "RecursCompf"