基本算法练习

• 快速排序
• 表达式求值

快速排序

基本思想 选择哨兵，将比它大的放到左边，小的放到右边。再对左右重复进行上述过程。

def fast_sort(seq, start, end):
    if start >= end:
        return seq
    # end选为哨兵
    sequential_idx = end
    left_idx = start
    right_idx = end - 1
    while left_idx < right_idx:
        if seq[left_idx] > seq[sequential_idx] and seq[right_idx] < seq[sequential_idx]:
            tmp = seq[left_idx]
            seq[left_idx] = seq[right_idx]
            seq[right_idx] = tmp
            left_idx += 1
            right_idx -= 1
        elif seq[right_idx] < seq[sequential_idx]:
            left_idx += 1
        elif seq[left_idx] > seq[sequential_idx]:
            right_idx -= 1
        else:
            left_idx += 1
            right_idx -= 1
    lower_idx = min([left_idx, right_idx])
    if seq[sequential_idx] > seq[lower_idx]:
        tmp = seq[sequential_idx]
        seq[sequential_idx] = seq[lower_idx + 1]
        seq[lower_idx + 1] = tmp
        fast_sort(seq, start, lower_idx)
        fast_sort(seq, lower_idx + 2, end)
    else:
        tmp = seq[sequential_idx]
        seq[sequential_idx] = seq[lower_idx]
        seq[lower_idx] = tmp
        fast_sort(seq, start, lower_idx - 1)
        fast_sort(seq, lower_idx + 1, end)
    return seq
    
if '__main__' == __name__:
    seq = [1,3,4,2,1]
    print(fast_sort(seq, 0, len(seq) - 1))
    seq = []
    print(fast_sort(seq, 0, len(seq) - 1))
    seq = [2,1]
    print(fast_sort(seq, 0, len(seq) - 1))
    seq = [2,1,1,1,1]
    print(fast_sort(seq, 0, len(seq) - 1))

[1, 1, 2, 3, 4]
[]
[1, 2]
[1, 1, 1, 1, 2]

表达式求值

给定一个带括号和加号的表达式，对其进行求值。

def eval(exp):
    symbol_stack = []
    exp_stack = []
    val_stack = [-1]
    for ch in exp:
        if ch == '(':
            symbol_stack.append(ch)
        elif ch == ')':
            exp = exp_stack.pop()
            right = val_stack.pop()
            left = val_stack.pop()
            if exp == '+':
                val_stack.append(right + left)
        elif ch == '+':
            exp_stack.append(ch)
        else:
            val_stack.append(int(ch))
    while len(exp_stack) > 0:
        right = val_stack.pop()
        left = val_stack.pop()
        if (exp_stack.pop() == '+'):
            val_stack.append(right + left)
    return val_stack.pop()

if __name__ == "__main__":
    print(eval('(1+2)+(4+5)+6'))

18