stack and queque

Infix, Prefix and Postfix Expressions

precedence level ? Setiap operator memiliki precedence level.

Maka Operasi perhitungannya mengikuti level dari precedence tersebut.

A + B * C + D = ((A + (B * C)) + D) à operator * lebih didahulukan daripada operator *, dan operator + yang pertama juga didahulukan daripada yang kedua (kiri ke kanan)

Jadi pronsip Precedence level adalah : Highest Precedence and Left to Right

Conversion of Infix Expressions to Prefix and Postfix

 à Post fix

 à Prefix

Baca setiap karakter notasi infix dari awal

 Bila operand maka langsung dicetak

 Bila tanda ‘(‘ masukkan stack

Bila tanda ‘)’ pop dan cetak semua isi stack sampai TOS = ‘(‘. Pop juga tanda ‘(‘ ini, tetapi tidak usah 

dicetak

Bila operator : jika stack kosong atau derajad operator lebih tinggi dibanding derajad TOS, push operator 

ke dalam stack. Jika tidak, pop dan cetak; kemudian ulangi pembandingan dengan TOS. Kemudian di-

push

( A + B ) / (( C – D ) * E ^ F) Ilustrasi pengubahan notasi infix di atas menjadi notasi postfix

Karakter dibaca

Isi Tumpukan

Karakter tercetak

Hasil Notasi Postfix Yang Terbentuk

from pythonds.basic.stack import Stack

def infixToPostfix(infixexpr):

    prec = {}

    prec["*"] = 3

    prec["/"] = 3

    prec["+"] = 2

    prec["-"] = 2

    prec["("] = 1

    opStack = Stack()

    postfixList = []

    tokenList = infixexpr.split()

    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)

print(infixToPostfix("A * B + C * D"))

print(infixToPostfix("( A + B ) * C - ( D - E ) * ( F + G )"))

Postfix Evaluation

from pythonds.basic.stack import Stack

def postfixEval(postfixExpr):

    operandStack = Stack()

    tokenList = postfixExpr.split()

    for token in tokenList:

        if token in "0123456789":

            operandStack.push(int(token))

        else:

            operand2 = operandStack.pop()

            operand1 = operandStack.pop()

            result = doMath(token,operand1,operand2)

            operandStack.push(result)

    return operandStack.pop()

def doMath(op, op1, op2):

    if op == "*":

        return op1 * op2

    elif op == "/":

        return op1 / op2

    elif op == "+":

        return op1 + op2

    else:

        return op1 - op2

print(postfixEval('7 8 + 3 2 + /'))