Evaluera postfix
Funktion för att räkna ut värdet (evaluera) av ett uttryck på postfix notation.
algoritm evaluera postfix
Vi läser vår postfix -lista från token till token.- Om vi läser en operand (siffra, variabel), lägger vi operanden på stacken. Push(operand).
- Om vi läser en operator då pop:ar vi 2 värden på stacken, kör operatorn på dessa värden och lägger sedan tillbaka resultatet på stacken.
Vi fortsätter tills bara ett värde ligger på stacken och det är resultatet.
import re
stack = []
def is_number(n):
try:
float(n)
except:
return False
return True
def prec(c):
if(c=='^'):
return(3)
if(c=='*' or c=='/'):
return(2)
if(c=='+' or c=='-'):
return(1)
return(0)
def infix2postfix(uttryck):
postfix = []
uttryck = uttryck.replace(" ", "")
infix = re.findall(r'([0-9\.]+|\*|\+|\-|\/|\(|\))', uttryck)
for c in infix:
if(is_number(c)):
postfix.append(c)
elif(c=='('):
stack.append('(')
elif(c==')'):
while(stack[len(stack)-1]!='('):
postfix.append(stack[-1])
stack.pop()
stack.pop()
else:
while(len(stack) > 0 and prec(c) <= prec(stack[-1])):
postfix.append(stack[-1])
stack.pop()
stack.append(c)
stk = " ".join(stack)
str = " ".join(postfix)
print('[{:<30}][{:<17}]'.format(str,stk));
while(len(stack) != 0):
postfix.append(stack[-1])
stack.pop()
stk = " ".join(stack)
str = " ".join(postfix)
print('[{:<30}][{:<17}]'.format(str,stk));
return(postfix)
def operator(n):
if(len(n)==1):
return(prec(n))
else:
return(0)
def evalPostfix(postfix):
for e in postfix:
if(operator(e)):
print(e)
b = stack[-1]
stack.pop()
if(len(stack)>0):
a = stack[-1]
stack.pop()
else:
a=0
if(e=='+'):
stack.append(float(a)+float(b))
if(e=='-'):
stack.append(float(a)-float(b))
if(e=='*'):
stack.append(float(a)*float(b))
if(e=='/'):
stack.append(float(a)/float(b))
if(e=='^'):
stack.append(int(a)**int(b))
else:
stack.append(e)
print(stack)
uttryck = "-(10*(30/(2+(0.0+0.5))))"
postfix = infix2postfix(uttryck)
evalPostfix(postfix)