Implementasi Infix Posfix Python

infix_posfix.py

# Class yang berfungsi sebagai ADT stack
class Stack:
    def __init__(self):
        self._stack = []
        self._top = -1

    def push(self, element):
        self._top += 1
        self._stack.insert(self._top, element)

    def pop(self):
        if self.is_empty():
            raise IndexError('Can not pop() from an empty Stack')
        self._top -= 1
        return self._stack[self._top + 1]

    def is_empty(self):
        return self._top == -1

    def peek(self):
        if self.is_empty():
            return None
        return self._stack[self._top]

# Konstanta pembantu

# ALPHABET berisi karakter A-Z dan a-z
ALPHABET = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
ALPHABET += ALPHABET.lower()
# NUMBERS berisi karakter 0-9
NUMBERS = '0123456789'
# OPS_CHARS_PRECENDENCE berisi keutamaan sebuah operator, operator yang memiliki
# nilai yang lebih tinggi mendapat keutamaan yang lebih tinggi pula
OPS_CHARS_PRECENDECE = {
    '(' : 3,
    '^' : 2,
    '/' : 1,
    '*' : 1,
    '+' : 0,
    '-' : 0,
}

# Definisikan dua stack untuk keperluan menyelesaikan
# ops_stack untuk menyimpan operator-operator
ops_stack = Stack()
# postfix_stack untuk menyimpan notasi posfix yang final
postfix_stack = Stack()

# Mengambil masukan pengguna
infix_str_list = input()

# Fungsi-fungsi pembantu
def is_operand(char):
    '''
    Berfungsi untuk mengecek apakah sebuah char adalah operand atau bukan.
    '''
    if char in (ALPHABET + NUMBERS):
        return True
    return False

def is_operator(char):
    '''
    Berfungsi untuk mengecek apakah sebuah char adalah operator atau bukan
    '''
    if char in OPS_CHARS_PRECENDECE.keys():
        return True
    return False

def is_op_has_higher_precedence(operator1, operator2):
    '''
    Berfungsi untuk mengecek apakah `operator1` memiliki keutamaan yang
    lebih tinggi daripada `operator2`.
    '''
    operator1_precedence = OPS_CHARS_PRECENDECE[operator1]
    operator2_precedence = OPS_CHARS_PRECENDECE[operator2]

    if operator1_precedence >= operator2_precedence:
        return True
    return False

# Loop utama
# element merupakan satu char dari masukan pengguna
# dapat berupa operand maupun operator
for element in infix_str_list:
    if is_operand(element):
        # Jika element ternyata adalah operand langsung masukkan saja
        # ke dalam postfix_stack
        postfix_stack.push(element)
    elif element == ')':
        # Jika element ternyata adalah kurung tutup maka pop semua operator
        # yang ada di dalam ops_stack ke dalam postfix_stack sampai ditemukan
        # tanda kurung buka
        op_top = ops_stack.pop()
        while (op_top != '('):
            postfix_stack.push(op_top)
            try:
                op_top = ops_stack.pop()
            except IndexError:
                # Jika ternyata stack sampai kosong dan tidak ditemukan tanda
                # kurung buka, maka ada tanda kurung yang tidak berpasangan.
                raise RuntimeError('Ada tanda kurung yang tidak berpasangan')
    elif is_operator(element):
        # Jika element adalah operator maka masukan ke dalam ops_stack
        while (not ops_stack.is_empty() and
               not ops_stack.peek() == '(' and
               is_op_has_higher_precedence(ops_stack.peek(), element)):
            # Sebelum memasukkan ke dalam ops_stack, cek dulu apakah ada
            # operator yang punya keutamaan lebih tinggi di element paling atas
            # stack daripada elemen yang sekarang dicek, jika ada maka
            # pop semua element yang ada memenuhi persyaratan tersebut di ops_stack
            # dan masukkan ke postfix_stack.
            postfix_stack.push(ops_stack.pop())
        ops_stack.push(element)

# Jika ada sisa dari ops_stack yang belum dipush ke postfix stack
# di loop utama maka pop ke postfix_stack sampai ops_stack kosong
while not ops_stack.is_empty():
    postfix_stack.push(ops_stack.pop())

print(''.join(postfix_stack._stack))