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 matches(open, close):
    opens = "{[("
    closes = "}])"
    return opens.index(open) == closes.index(close)


def check(strings):
    s = Stack()
    index = 0
    while index < len(strings):
        a = strings[index]
        if a in "{[(":
            s.push(a)
        else:
            if s.isEmpty():
                return False
            else:
                top = s.pop()
                if not matches(top, a):
                    return False
        index += 1

    if s.isEmpty():
        return True
    else:
        return False


"""
进制转换
"""


def translate1(num):
    s = Stack()
    while num > 0:
        a = num % 2  # 取余
        s.push(a)
        num = num // 2  # 整除
    string = ""
    while not s.isEmpty():
        string = string + str(s.pop())

    return string


def translate2(num, n):  # 转n进制
    s = Stack()
    while num > 0:
        a = num % n  # 取余
        s.push(a)
        num = num // n  # 整除
    string = ""
    while not s.isEmpty():
        string = string + str(s.pop())

    return string


"""
中缀表达式 传 前缀表达式
"""


def infix1(infixexpr):
    # 记录操作符的优先级
    prec = {}
    prec["*"] = 3
    prec["/"] = 3
    prec['+'] = 2
    prec['-'] = 2
    prec["("] = 1
    opstack = Stack()
    lists = []
    tokenlist = infixexpr.split()  # 解析表达式到的单词列表

    for token in tokenlist:
        if token in "ABCDEFGHIJKLMNOPQRSTUVWXYZ" or token in "0123456789":
            lists.append(token)
        elif token == "(":
            opstack.push(token)
        elif token == ')':
            top = opstack.pop()
            while top != '(':
                lists.append(top)
                top = opstack.pop()
        else:
            while(not opstack.isEmpty()) and (prec[opstack.peek()] >= prec[token]):
                lists.append((opstack.pop()))
            opstack.push(token)

    while not opstack.isEmpty():
        lists.append(opstack.pop())

    print(''.join(lists))
    return ''.join(lists)


"""
后缀表达式求值
"""


def domath(a, t1, t2):
    if a == "*":
        return t1 * t2
    elif a == '/':
        return t1 * t2
    elif a == "+":
        return t1 + t2
    else:
        return t1 - t2


def infix2(infixexpr):
    opstack = Stack()
    tokenlist = infixexpr.split()  # 解析表达式到的单词列表

    for token in tokenlist:
        if token in "0123456789":
            opstack.push(int(token))
        else:
            t1 = opstack.pop()
            t2 = opstack.pop()
            res = domath(token, t1, t2)
            opstack.push(res)
    return opstack.pop()