应用stack结构的算法

计算机软件的运行，是离不开调用栈的。操作调用栈的相关代码由编译器生成，程序员一般情况下看不到。除此之外，LIFO就是栈。以下是个人工作学习中，遇到应用stack数据结构的情况。

我们熟悉和日常所见所写的算术运算表达式，都是infix格式的，即操作符在数字中间，这是人类能够容易理解的格式，中文称之为中缀表达式。如果让计算机对infix格式进行计算，有难度（我记得大学时，我采用了递归的方法来计算，即遇到括号就递归，可惜代码遗失了）！简单点的方法，就是采用postfix表达式，中文称之为后缀表达式。

postfix format，aka reverse polish notation，逆荷兰表达式，如下：

infix: 1+2*3
postfix: 123*+

infix: (1+2)*3
postfix: 12+3*

infix: 2*(3+4*5)
postfix: 2345*+*

postfix表达式把所有括号都去掉了。计算机对postfix格式进行计算，只需要简单使用一个stack数据结构，遇到操作符，就pop操作数出来计算，然后将结果push。比较有趣的是，我们同样使用stack结构，可以将infix格式转换成postfix格式。

这个实现存在一个问题：比如-1，会被修改为1-。需要将最开始的负数，写成0-的形式。更简单的预处理，将所有-T，替换成(0-T)。

opp = {'+':0, '-':0,
       '*':1, '/':1,
       '^':2}


def infix2postfix(expr: str) -> str:
    ops = []
    postfix = []
    # one pass scan
    for c in expr:
        if c == ' ':
            continue
        if c.isdigit():
            postfix.append(c)
            continue
        # supported operators
        assert c in ('+','-','*','/','(',')','^')
        if c == '(':
            ops.append(c)
            continue
        elif c == ')':
            while (t:=ops.pop()) != '(':
                postfix.append(t)
            continue
        elif len(ops)==0 or ops[-1]=='(':
            ops.append(c)
            continue
        else:
            if opp[c] > opp[ops[-1]]:
                ops.append(c)
            else:
                while (len(ops) and
                        ops[-1] in opp and
                        opp[c]<=opp[ops[-1]]):
                    postfix.append(ops.pop())
                ops.append(c)
    return ''.join(postfix) + ''.join(ops[::-1])


from unittest import TestCase
tc = TestCase()
tc.assertEqual(infix2postfix(''), '')
tc.assertEqual(infix2postfix('1'), '1')
tc.assertEqual(infix2postfix('1 + 2'), '12+')
tc.assertEqual(infix2postfix('( 1 + 2 )'), '12+')
tc.assertEqual(infix2postfix('1 + 2 - 3'), '12+3-')
tc.assertEqual(infix2postfix('1 + ( 2 - 3 )'), '123-+')
tc.assertEqual(infix2postfix('1 + 2 * 3'), '123*+')
tc.assertEqual(infix2postfix('1 / 2 + 3 * 4'), '12/34*+')
tc.assertEqual(infix2postfix('1 * 2 * 3 + 4'), '12*3*4+')
tc.assertEqual(infix2postfix('1 + 2 * 3 * 4'), '123*4*+')
tc.assertEqual(infix2postfix('1 * ( 2 + 3 ) * 4'), '123+*4*')
tc.assertEqual(infix2postfix('1 * ( 2 + 3 * 4 ) + 5'), '1234*+*5+')
tc.assertEqual(infix2postfix('1*((2+3)*4)*(5-6)'), '123+4**56-*')
tc.assertEqual(infix2postfix('1*((((2))+3)*4)*(5-6)'), '123+4**56-*')
tc.assertEqual(infix2postfix('0-1'), '01-')

tc.assertEqual(infix2postfix('1^3+2'), '13^2+')
tc.assertEqual(infix2postfix('(1+2)^3'), '12+3^')
tc.assertEqual(infix2postfix('1+2^3'), '123^+')
tc.assertEqual(infix2postfix('1^2^3'), '12^3^')
tc.assertEqual(infix2postfix('1^(2^3)'), '123^^')
tc.assertEqual(infix2postfix('1^(2^(3^4))'), '1234^^^')
tc.assertEqual(infix2postfix('1+(2-3)^4'), '123-4^+')
tc.assertEqual(infix2postfix('1-2^(3+4)'), '1234+^-')
tc.assertEqual(infix2postfix('1/2*8+3/9*4'), '12/8*39/4*+')
tc.assertEqual(infix2postfix('1/2^8+3^9*4'), '128^/39^4*+')
tc.assertEqual(infix2postfix('1*2^9*3+4'), '129^*3*4+')
tc.assertEqual(infix2postfix('1+2*3^9*4/5'), '1239^*4*5/+')
tc.assertEqual(infix2postfix('1^((2+3)*4)+5'), '123+4*^5+')
tc.assertEqual(infix2postfix('(1*((2+3)^4))^(5-6)'), '123+4^*56-^')
tc.assertEqual(infix2postfix('1*((((2))+3)*4)*(5-6)'), '123+4**56-*')
tc.assertEqual(infix2postfix('(0-1)^(0-2)'), '01-02-^')

tc.assertEqual(infix2postfix('(9-1-1)/7'), '91-1-7/')

计算postfix格式

def eval_postfix(pstr: str) -> str:
    stack = []
    for c in pstr:
        if c in opp.keys():
            a = stack.pop()
            b = stack.pop()
            # b must be in the first place due to -,/,^
            c = '**' if c=='^' else c
            stack.append(str(eval(b+c+a)))
        else:
            stack.append(c)
    return stack.pop()


assert eval_postfix(infix2postfix('1+2')) == '3'
assert eval_postfix(infix2postfix('(1+2)*3')) == '9'
assert eval_postfix(infix2postfix('(1+2)*3/3')) == '3.0'
assert eval_postfix(infix2postfix('(1+2)*3/(2+1)')) == '3.0'
assert eval_postfix(infix2postfix('(1+(1+1))*3/(2+1)')) == '3.0'
assert eval_postfix(infix2postfix('(1+(1+1-1+1))*3/(1+1+1)')) == '3.0'
assert eval_postfix(infix2postfix('(9-1-1)/7')) == '1.0'
assert eval_postfix(infix2postfix('(1+2)*(3+4)')) == '21'
assert eval_postfix(infix2postfix('((1)+(2))*((3)+(4))')) == '21'
assert eval_postfix(infix2postfix('(1+2)*(3+4)*(2-1-((0-0)-0))')) == '21'
assert eval_postfix(infix2postfix('(1+2)*(3/1+4)*(2-1-((0-0)-0))')) == '21.0'
assert eval_postfix(infix2postfix('(1/1+2/1)*(3/1+4/1)*(2/1-1/1-((0/1-0/1)-0/1))')) == '21.0'

assert eval_postfix(infix2postfix('1^2')) == '1'
assert eval_postfix(infix2postfix('(1+2)^3')) == '27'
assert eval_postfix(infix2postfix('(1+2)^3/3')) == '9.0'
assert eval_postfix(infix2postfix('3*(1+2)^(3+4)')) == str(3*3**7)

postfix结构转Expression Tree

遍历BSTree

另一个stack的应用，纯用循环方式实现BSTree，__iter__接口的实现，用到了stack结构辅助！stack结构有记忆功能，它可以记住来时的路，并可一步步返回。

应用stack结构的算法

生成算术表达式的postfix格式

计算postfix格式

postfix结构转Expression Tree

遍历BSTree

对Trie结构的操作