应用stack结构的算法

Last Updated: 2023-08-31 13:38:42 Thursday

-- TOC --

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

stack有记忆功能,它能记住你来时的路...

生成算术表达式的postfix格式

我们熟悉和日常所见所写的算术运算表达式,都是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格式。

下面是我的Python实现和测试,这个版本支持幂运算符号^:

这个实现存在一个问题:比如-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格式

转换了计算postfix格式的表达式,都是用stack!

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)

减法-,除法/和幂运算^,都稍微有点特殊,对顺序敏感!

Python内置的list,就是非常好用的stack结构。

遍历BSTree

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

对Trie结构的操作

操作Trie结构时,remove接口要使用stack结构。

参考:详解Trie结构和实现

本文链接:https://cs.pynote.net/ag/202308025/

-- EOF --

-- MORE --