r/DailyProgrammer 196 hard

ch196hard.py

OP_LEFT_FIRST = 0
OP_LEFT_SECOND = 1
OP_ORDER = {'.': -1, '<': 0, '>': 0, '+': 1, '-': 1, '*': 2, '/': 2, '%': 2, '^': 3, '&': 3, '|': 3}


def solve(test):
    items = []
    ops = []
    for elem in test['eq']:
        if is_num(elem):
            items.append(elem)
        elif elem == '(':
            ops.append(elem)
        elif elem == ')':
            while len(ops) > 0:
                op_left = ops.pop()
                if op_left == '(':
                    break
                combine(items, op_left)

        else:
            if len(ops) > 0:
                while len(ops) > 0:
                    prev_op = ops.pop()
                    if op_order(prev_op, elem, test['prec']) == OP_LEFT_FIRST:
                        combine(items, prev_op)
                    else:
                        ops.append(prev_op)
                        break
            ops.append(elem)

    while len(ops):
        combine(items, ops.pop())

    return items.pop()


def combine(items, op):
    val_right = items.pop()
    val_left = items.pop()
    items.append("(" + str(val_left) + op + str(val_right) + ")")


def op_order(op_left, op_right, rule):
    if op_left == '(':
        return OP_LEFT_SECOND

    if op_left != op_right:
        return OP_LEFT_FIRST if OP_ORDER[op_left] > OP_ORDER[op_right] else OP_LEFT_SECOND

    if rule.has_key(op_left):
        return OP_LEFT_FIRST if rule[op_left] == 'left' else OP_LEFT_SECOND

    return OP_LEFT_SECOND


def is_num(elem):
    try:
        float(elem)
        return True
    except:
        return False


if __name__ == '__main__':
    tests = [
        {
            'prec': {
                '^': 'right',
                '*': 'left',
                '+': 'left',
            },
            'eq': '1+2*(3+4)^5+6+7*8',
        },
        {
            'prec': {
                '&': 'left',
                '|': 'left',
                '^': 'left',
                '<': 'right',
                '>': 'right',
            },
            'eq': '3|2&7<8<9^4|5',
        },
        {
            'prec': {
                '<': 'left',
                '>': 'right',
                '.': 'left',
            },
            'eq': '1<1<1<1<1.1>1>1>1>1',
        },
        {
            'prec': {
                '*': 'left',
                '+': 'left',
            },
            'eq': '1+1*(1+1*1)',
        }
    ]
    for test in tests:
        print(test['eq'])
        print(solve(test))