У меня есть префиксное выражение, которое имеет только 4 бинарных оператора (+,-,*,/). Прямой способ оценить такое выражение - преобразовать его в постфиксное выражение, а затем оценить это выражение. Но я ищу алгоритм, который делает это напрямую, не преобразовывая его в какое-либо другое выражение?
Алгоритм для оценки префиксного выражения?
comment
Вы уверены, что ваше выражение является префиксом? Можете ли вы вставить несколько примеров? Инфиксные выражения трудно вычислить, и они обычно преобразуются в постфиксные.
- person Amir Afghani schedule 16.02.2013
Ответы (2)
Простая рекурсия:
Evaluate(input):
Read a token from input.
If the token is a value:
Return the value of the token
If the token is a binary operator:
Let first_argument = Evaluate(input)
Let second_argument = Evaluate(input)
Return apply(operator, first_argument, second_argument)
person
rici
schedule
16.02.2013
Используйте стек. Разместите свои переменные и операторы и начните извлекать каждый стек, один для операторов, а другой для varaiablss (количество извлечений зависит от арности).
person
Srikant Krishna
schedule
16.02.2013
Это довольно расплывчатый ответ. У вас есть какие-нибудь источники?
- person ; 16.02.2013
Она называется моделью автоматов выталкивания вниз.
- person Srikant Krishna; 16.02.2013
