Недавно попался на глаза "калькулятор", который я бы лучше назвал eval'ютором.
Задачка вроде как затасканная, что и говорить, даже в книжке Страуструпа есть ее решение. Я никогда ничего подобного не писал, в примере Страуструпа не сильно разбирался (по причине того, что не люблю я всякие сложные рекурсивные парсеры), поэтому сел и написать все с нуля на питоне (заодно и освежил знания языка, давно ничего не писал на нем).
Код написал без особых проблем и заработал он сразу, правда потратил я на все это дело пару часов точно. После того как код заработал, я сделал небольшой рефакторинг, потому что несколько промахнулся с дизайном -- у меня появился непонятно о чем класс с называнием Element, который был сразу и обо всем, состоящий чуть больше, чем полностью, из ассертов. Класс ушел в мусорку, в итоге появилось понятие Item -- нечто, что может быть или числом (Number), или унарной операцией (OpUnary), или операцией бинарной (OpBinary).
Код получился относительно простым и понятным.
Работает все это так.
Сначала я делаю парсинг -- разбиваю исходную строку с выражением на массив строк, каждая из которых есть логически законченный атомарный элемент синтаксиса. Разбиваю просто -- ищу в строке операторы, а потом их использую как точки для дробления исходной строки. Находится все это в функции Parse (это название мне подсказал К.О.).
Второй этап -- трансформация списка строк в список Item'ов.
На этом этапе я делаю следующие вещи.
#1. Выбрасываю скобки, и использую их для выставления приоритета бинарный операций (см. ниже).
#2. Преобразую идентификаторы (имена переменных) в их значения.
#3. Порождаю числа (класс Number).
#3. Порождаю унарные операторы. Оператор унарный, если слева от него стоит не число, а другой оператор.
#4. Порождаю бинарные операторы. Каждая из операций имеет базовый приоритет, описанный в словаре с операторами, рядом с функциями, которые имплементируют сам оператор (COpsBinary). При создании оператора его приоритет равен базовому приоритету оператора плюс бонус за уровень скобок, умноженный на некую константу, заведомо большую любого базового приоритета оператора. Например, если приоритет сложения равен 1, константа для скобок равна 10, то оператор "+" стоящий за двумя скобками получит приоритет 1 + 10 * 2.
Код второго этапа находится в функции FirstPass.
Дальше идут два вычислительных этапа -- сначала вычисление всех унарный операций, потом всех бинарных.
Унарные операторы считаются просто -- если слева от числа стоит унарная операция, ее надо вычислить. Повторять до тех пор, пока в списке есть унарные операции. Функция -- ProcessUnary.
Бинарные операторы считаются так -- найти оператор с самым высоким приоритетом и посчитать его. Повторять до тех пор, пока в списке есть операторы. Соответственно, функция ProcessBinary.
Вот и все. Никаких рекурсий, польских записей и прочих вещей.
Кода получилось довольно много (некоторые в меньший объем интерпретатор Lisp'а умудряются засунуть!), дык такого рода алгоритмы не мой конек, написал как умел, гуру-функциональщики -- пинайте!
зы. Листинг
Copy Source | Copy HTML
import copy
# ------------------------------------------------------
def _FindInStr(s : str, values : [str]) -> [int]:
res = []
pos = 0
while pos < len(s):
for v in values:
if s[pos:pos + len(v)] == v:
res.append(pos)
break
pos += 1
return res
# ------------------------------------------------------
def Eval(exp : str, vars : dict) -> float:
CParenthesisBonus = 10
COpsUnary = {
'-': lambda x: -x
}
# (priority, lambda); priority must > 0 and < CParenthesisBonus
COpsBinary = {
'-': (1, lambda x, y: x - y),
'+': (1, lambda x, y: x + y),
'*': (2, lambda x, y: x * y),
'/': (2, lambda x, y: x / y),
}
# one of Number, OpUnary, OpBinary
class Item: pass
class Number(Item):
def __init__(self, val : str or float):
self.val = float(val)
def Val(self) -> float:
return self.val
class OpUnary(Item):
def __init__(self, val : str):
self.val = val
self.calcFn = COpsUnary[val]
def Calc(self, num : Number) -> Number:
return Number( self.calcFn(num.Val()) )
class OpBinary(Item):
def __init__(self, val : str, psisLevel : int):
self.val = val
desc = COpsBinary[val]
self.prio = desc[ 0] + psisLevel * CParenthesisBonus
self.calcFn = desc[1]
def Calc(self, num0, num1 : Number) -> Number:
return Number( self.calcFn(num0.Val(), num1.Val()) )
def Priority(self): return self.prio
def Parse(exp : str) -> [str]:
def Add(s : str):
s = s.strip()
if not s: return
res.append(s)
CSpliters = ['(', ')', '-', '+', '*', '/']
nodes = _FindInStr(exp, CSpliters)
assert len(nodes)
res = []
if nodes[ 0] > 0:
Add( exp[:nodes[ 0]] )
for indx, n in enumerate(nodes):
Add( exp[n] ) # add node
if indx + 1 < len(nodes):
Add( exp[n + 1 : nodes[indx + 1]] )
else:
Add( exp[n + 1 : ] )
return res
def FirstPass(lx : [str]) -> [Item]:
""" remove parenthesis, setup vars, makes items """
res = []
psisLevel = 0
for s in lx:
if s == '(':
psisLevel += 1
continue
if s == ')':
assert psisLevel > 0
psisLevel -= 1
continue
if s[ 0].isdigit():
res.append( Number(s) )
continue
if s[ 0].isalpha():
res.append( Number(vars[s]) )
continue
# s is operator
if len(res) == 0 or not isinstance(res[len(res)-1], Number):
res.append( OpUnary(s) )
else:
res.append( OpBinary(s, psisLevel) )
assert psisLevel == 0
return res
def ProcessUnary(lx : [Item]) -> [Item]:
def FindUnaryNextToNumber() -> int:
for indx, i in enumerate(lx):
if not isinstance(i, OpUnary): continue
if isinstance(lx[indx + 1], Number):
return indx
return -1
lx = copy.copy(lx)
while True:
indx = FindUnaryNextToNumber()
if indx < 0: break
res = lx[indx].Calc( lx[indx+1] )
lx = lx[:indx] + [res] + lx[indx + 2:]
return lx
def ProcessBinary(lx : [Item]) -> [Item]:
def FindHighestPrioOp() -> int:
maxIndx = -1
maxPrio = 0
for indx, i in enumerate(lx):
if isinstance(i, OpBinary) and i.Priority() > maxPrio:
maxIndx = indx
maxPrio = i.Priority()
return maxIndx
lx = copy.copy(lx)
while True:
indx = FindHighestPrioOp()
if indx < 0: break
res = lx[indx].Calc( lx[indx-1], lx[indx+1] )
lx = lx[:indx-1] + [res] + lx[indx + 2:]
return lx
lx = Parse(exp)
lx = FirstPass(lx)
lx = ProcessUnary(lx)
lx = ProcessBinary(lx)
assert len(lx) == 1
return lx[ 0].Val()
# ------------------------------------------------------
def PyEval(exp : str, vars : dict) -> float:
return eval(exp, vars)
# ------------------------------------------------------
def Test(exp : str, vars : dict):
res = Eval(exp, vars)
resRef = PyEval(exp, vars)
if res != resRef:
raise Exception( "{0} != {1}".format(res, resRef) )
print("OK, " + str(res))
# ------------------------------------------------------
if __name__ == "__main__":
CExp = '16 - (-a + 10 * b)+7*--c'
CVars = {'a':1, 'b':2, 'c':-15}
Test(CExp, CVars)
No comments:
Post a Comment