class Stack(object):
    """栈的 Python 列表实现
    """
    # 初始化对象，生成空列表
    def __init__(self):
        self.item = []

    # 判断栈是否为空，返回 True or False
    def isEmpty(self):
        return self.item == []

    # 入栈方法，添加至列表尾部
    def push(self, item):
        self.item.append(item)

    # 出栈方法，从队列尾部弹出，并返回弹出值
    def pop(self):
        return self.item.pop()

    # 查栈顶元素方法，返回栈顶元素值，但不弹出
    def peek(self):
        return self.item[len(self.item)-1]

    # 查看栈的大小方法，返回 int 值
    def size(self):
        return len(self.item)

def match_sympol(string):
    """
    利用栈的特性（后进先出），对三种常见括号进行匹配
    对于左括号，直接压入栈，遇到右括号，弹出栈顶元素，若能一一对应，且最终栈为空，则完全匹配
    """
    s = Stack()
    flag = True
    index = 0
    while index < len(string) and flag:
        symbol = string[index]
        if symbol in "({[":
            s.push(symbol)
        else:
            if s.isEmpty():
                flag = False
            else:
                top = s.pop()
                if not matches_help(top, symbol):
                    flag = False
        index += 1

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

def matches_help(open, close):
    """
    匹配辅助函数
    传入两个 char 参数，判断是否对应，返回 True or False
    """
    opens = "({["
    closes = ")}]"
    return opens.index(open) == closes.index(close)

def ten2two(num):
    """
    十进制转二进制，原理是除二取余法
    将十进制数除二取余数，将余数压入栈，直到十进制数为 0，然后栈逐个弹出
    """
    s = Stack()

    while num > 0:
        rem = num%2
        s.push(rem)
        num = num//2

    binString = ""
    while not s.isEmpty():
        binString = binString + str(s.pop())

    return binString

def infixToPostfix(infixexpr):
    """
    中序表达式转后续表达式
    中序表达式转换后续表达式有个简单的方法，先将中序表达式的每一次运算都加上括号，接着从右往左，
    找到第一个算数符号替换掉最近的右括号，并将对应的左括号去除，继续往左执行，直到没有括号为止
    具体过程：
    1、创建一个名为 opstack 的空栈以保存运算符。给输出创建一个空列表。
    2、通过使用字符串方法拆分将输入的中缀字符串转换为标记列表。
    3、从左到右扫描标记列表。
          如果标记是操作数，将其附加到输出列表的末尾。
          如果标记是左括号，将其压到 opstack 上。
          如果标记是右括号，则弹出 opstack，直到删除相应的左括号。将每个运算符附加到输出列表的末尾。
          如果标记是运算符，*，/，+或 - ，将其压入 opstack。但是，首先删除已经在 opstack 中具有更高或相等优先级的任何运算符，并将它们加到输出列表中。
    4、当输入表达式被完全处理时，检查 opstack。仍然在栈上的任何运算符都可以删除并加到输出列表的末尾。
    理解过程可见：https://facert.gitbooks.io/python-data-structure-cn/3.%E5%9F%BA%E6%9C%AC%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/3.9.%E4%B8%AD%E7%BC%80%E5%89%8D%E7%BC%80%E5%92%8C%E5%90%8E%E7%BC%80%E8%A1%A8%E8%BE%BE%E5%BC%8F/
    """
    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)

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):
    """
    后缀表达式运算值的辅助函数
    输入三个参数（运算符，操作数1，操作数2），返回运算结果。
    """
    if op == "*":
        return op1 * op2
    elif op == "/":
        return op1 / op2
    elif op == "+":
        return op1 + op2
    else:
        return op1 - op2

#栈的测试
# s= Stack()
# print(s.isEmpty())
# s.push(4)
# s.push('dog')
# print(s.peek())
# s.push(True)
# print(s.size())
# print(s.isEmpty())
# s.push(8.4)
# print(s.pop())
# print(s.pop())
# print(s.size())
# 符号匹配的测试
# print(match_sympol(''))
# 十进制数转二进制的测试
# print(ten2two(100))
# 中缀表达式转后缀表达式的测试
# print(infixToPostfix("( A + B ) * C - ( D - E ) * ( F + G )"))
# 后缀表达式的求求值
# print(postfixEval('7 8 + 3 2 + /'))