Prefix

Definisi

Prefix ialah suatu metode penulisan dengan meletakkan operator di depan operand dan tanpa menuliskan tanda kurung (). Contohnya - * + A B C * - D E + F G

Ilustrasi

Algoritma

1. Pengerjaan dalam kurung pertama ( A + B ) , prefix nya adalah +AB
2. Pengerjaan dalam kurung kedua ( C - D ) , prefix nya adalah -CD
3. Pengerjaan yang terakhir adalah operator * , +AB * -CD, prefix nya adalah *+AB-CD

Kode Program
 def Stack():
    opStack=[]
    return opStack
   
def push(opStack,data):
    opStack.append(data)
   
def pop(opStack):
    data = opStack.pop()
    return data
  
def peek(opStack):
    return opStack[len(opStack)-1]
       
def isEmpty(opStack):
    return opStack == []
   
def size(opStack):
    return len(opStack)

   
def infixToPrefix(infixexpr):
    prec = {}
    prec["*"] = 3
    prec["/"] = 3
    prec["+"] = 2
    prec["-"] = 2
    prec["("] = 1
    prec[")"] = 1
    opStack = Stack()
    prefixList = []
    tokenList = infixexpr.split()
    hasil=' '
    step = 0
    for token in tokenList:
        if token in "ABCDEFGHIJKLMNOPQRSTUVWXYZ" or token in "0123456789":
            prefixList.append(token)
        elif token == ')':
            push(opStack,token)
        elif token == '(':
            topToken = pop(opStack)
            while topToken != ')':
                prefixList.append(topToken)
                topToken = opStack.pop()
           
       
        else:
            while (not isEmpty(opStack)) and \
               (prec[peek(opStack)]>= prec[token]):
                  prefixList.append(opStack.pop())
            push(opStack,token)
    while not isEmpty(opStack):
        prefixList.append(opStack.pop())
   
    return hasil.join(prefixList[::-1])
   
   
infix = "( A + B ) * C - ( D - E ) * ( F + G )"
infix_balik = infix[::-1]
print(infix)
print(infixToPrefix(infix_balik))