вот вам для затравки:
Я сделал набросок на питоне чтобы продемострировать как работает такой алгоритм.
Вот резальтаты:
(5 * (0 + ((5 * 5) - (9 / 7))))
(5 * ((0 + (5 * 5)) - (9 / 7)))
(5 * (((0 + 5) * 5) - (9 / 7)))
((5 + 0) * ((5 * 5) - (9 / 7)))
((5 - 0) * ((5 * 5) - (9 / 7)))
Вот программа. Разбирайтесь
| Код |
#!/usr/bin/env python
from string import atoi
sq = ['5','0','5','5','9','7']
res = 120
def convert_to_normal(postfix):
stack = []
for node in postfix:
if (node in ['*','/','+','-']):
n1 = stack[-1]
del(stack[-1])
n2 = stack[-1]
del stack[-1]
stack.append("(%s %s %s)"%(n2,node,n1))
else:
stack.append(node)
return stack[-1]
def evaluate_postfix(postfix):
stack = []
for node in postfix:
if (node == '*'):
n1 = stack[-1]
del(stack[-1])
n2 = stack[-1]
del stack[-1]
stack.append(n2 * n1)
elif (node == '+'):
n1 = stack[-1]
del(stack[-1])
n2 = stack[-1]
del stack[-1]
stack.append(n2 + n1)
elif (node == '-'):
n1 = stack[-1]
del(stack[-1])
n2 = stack[-1]
del stack[-1]
stack.append(n2 - n1)
elif (node == '/'):
n1 = stack[-1]
del(stack[-1])
n2 = stack[-1]
del stack[-1]
if (n1 == 0):
stack.append(0)
else:
stack.append(n2 / n1)
else:
stack.append(atoi(node))
return stack[-1]
def workout(src, r,stacksize, postfix):
if ( stacksize == 1) and (len(src) == 0):
if (evaluate_postfix(postfix) == r):
print convert_to_normal(postfix)
return
if (len(src)>0):
head = src[0]
tail = src[1:]
workout(tail,r,stacksize+1,postfix+[head])
if (stacksize >= 2):
workout(src,r,stacksize-1,postfix+['*'])
workout(src,r,stacksize-1,postfix+['/'])
workout(src,r,stacksize-1,postfix+['+'])
workout(src,r,stacksize-1,postfix+['-'])
workout(sq,120,0,[])
|
здесь есть одна небрежность - деление на 0 у меня дает 0 (это просто лень обрабатывать эту ситуацию) так что будьте внимательнее когда будете разбираться |
)