STRUKTUR DATA - INFIX, PREFIX, POSTFIX EXPRESSIONS Python
STRUKTUR DATA - Infix,
Prefix dan Postfix Expressions
Maka Operasi calculnyafore level dari presedensi tersebut.
A + B * C + D = ((A + (B * C)) + D) → operator * lebih didahulukan dari operator *, dan operator + yang pertama juga didahulukan fungsi yang kedua (kiri ke kanan).
Jadi pronsip Tingkat precedence adalah : Presedensi Tertinggi dan Kiri ke Kanan.
def stack():
s=[]
return (s)
def push(s,data):
s.append(data)
def pop(s):
data=s.pop()
return (data)
def peek(s):
return(s[len(s)-1])
def isEmpty(s):
return(s==[])
def size (s):
return(len(s))
def isOperand(x):
return (ord(x)>=ord('a')and ord(x)<=ord('z'))or(ord(x)>=ord('A')and ord(x)<=ord('Z'))
def Infix(x):
s=stack()
for i in range(len(x)):
if isOperand(x[i]):
temp=x[i]
push(s,temp)
else:
temp1=pop(s)
temp2=pop(s)
hasil=("("+temp2+x[i]+temp1+")")
push(s,hasil)
return peek(s)
print("Hasil = ",Infix("ABC+*"))
Kami menggunakan hal yang sama untuk mengubah Infix to Prefix.
Maka Operasi calculnyafore level dari presedensi tersebut.
A + B * C + D = ((A + (B * C)) + D) → operator * lebih didahulukan dari operator *, dan operator + yang pertama juga didahulukan fungsi yang kedua (kiri ke kanan).
Jadi pronsip Tingkat precedence adalah : Presedensi Tertinggi dan Kiri ke Kanan.
- PostFixEvaluation
def stack():
s=[]
return (s)
def push(s,data):
s.append(data)
def pop(s):
data=s.pop()
return (data)
def peek(s):
return(s[len(s)-1])
def isEmpty(s):
return(s==[])
def size (s):
return(len(s))
def isOperand(x):
return (ord(x)>=ord('a')and ord(x)<=ord('z'))or(ord(x)>=ord('A')and ord(x)<=ord('Z'))
def Infix(x):
s=stack()
for i in range(len(x)):
if isOperand(x[i]):
temp=x[i]
push(s,temp)
else:
temp1=pop(s)
temp2=pop(s)
hasil=("("+temp2+x[i]+temp1+")")
push(s,hasil)
return peek(s)
print("Hasil = ",Infix("ABC+*"))
- Infix to Prefix
Kami menggunakan hal yang sama untuk mengubah Infix to Prefix.
• Langkah 1: Membalikkan ekspresi infiks yaitu A + B
* C akan menjadi C * B + A. Catatan saat membalik masing-masing '(' akan
menjadi ')' dan masing-masing ')' menjadi '('.
• Langkah 2: Dapatkan ekspresi postfix dari ekspresi
yang dimodifikasi yaitu CB * A +.
• Langkah 3: Membalikkan ekspresi postfix. Maka dalam
contoh kita awalan adalah + A * BC.
class Stack:
def __init__(self):
self.items = []
def isEmpty(self):
return self.items == []
def push(self, item):
self.items.append(item)
def pop(self):
return self.items.pop()
def peek(self):
return self.items[len(self.items)-1]
def size(self):
return len(self.items)
def infixToPostfix(infixexpr):
prec = {}
prec["*"] = 3
prec["/"] = 3
prec["+"] = 2
prec["-"] = 2
prec["("] = 1
opStack = Stack()
postfixList = []
tokenList = infixexpr
for token in tokenList:
if token in
"ABCDEFGHIJKLMNOPQRSTUVWXYZ" or token in "0123456789":
postfixList.append(token)
elif token == '(':
opStack.push(token)
elif token == ')':
topToken = opStack.pop()
while topToken != '(':
postfixList.append(topToken)
topToken = opStack.pop()
else:
while (not opStack.isEmpty()) and \
(prec[opStack.peek()] >=
prec[token]):
postfixList.append(opStack.pop())
opStack.push(token)
while not opStack.isEmpty():
postfixList.append(opStack.pop())
return " ".join(postfixList)
infix = "A * ( B + C )
* D"
infix=infix[::-1]
infix=infix.split()
for i in range(len(infix)):
if infix[i] == '(':
infix[i]=')'
elif infix[i] == ')':
infix[i]='('
print(infix)
prefix=infixToPostfix(infix)
prefix=prefix[::-1]
print(prefix)
Komentar
Posting Komentar