算法笔记——四则运算

坑太多.exe

用例

• 1010+8-6-2+10-7+1+8+(1+6+(99)*8+1) 768
• 3+2{1+2[-4/(8-6)+7]} 25

思路

1. 把输入的字符串处理为数字和运算符组成的列表
2. 循环遍历列表 找到左括号时 进行递归 直到没有不再遇到左括号
3. 按乘除优先级高于加减 进行运算 并将结果覆盖参与运算的后者
4. 删除 参与运算的前者和运算符 返回前删除左右括号
5. 子一级，也就是括号内的结果运算完成 则把当前这一级进行同样的运算
6. 再次返回给上一级 或者发现列表被删除只剩一个 也就是最终运算结果 跳出
7. 得到最终计算结果

def convert(texts: str) -> list:
    tmp = ""
    _text = []
    texts = texts.replace(" ", "").replace("{", "(").replace("}", ")").replace("[", "(").replace("]", ")")
    for index, char in enumerate(texts):
        if char == "(":
            pass
        elif char == ")":
            if tmp != "":
                _text.append(int(tmp))
                tmp = ""
        elif char in ["+", "-", "*", "/"]:
            if texts[index - 1] == "(":
                _text.append(0)
            if tmp != "":
                _text.append(int(tmp))
                tmp = ""
        else:
            tmp += char
            continue
        _text.append(char)
    if tmp != "":
        _text.append(int(tmp)) 
    return _text

def calc(text: list, offset: int):
    while True:
        if text[offset] == "(":
            text = calc(text, offset+1)
        prepop = []
        _offset = offset
        while _offset >= offset and _offset < len(text) - 1: # 处理乘除
            if _offset in prepop: continue # 已经参与过运算 跳过
            if text[_offset + 1] == "(": # 当前位置的下一位是左括号 那么进行递归
                text = calc(text, _offset + 1 + 1) # 递归的起始offset是左括号后一位
            # 当前符号是乘或除 那么将符合前后进行运算 将结果放到后者
            if text[_offset] == "*":
                text[_offset + 1] = text[_offset - 1] * text[_offset + 1]
            elif text[_offset] == "/":
                text[_offset + 1] = text[_offset - 1] / text[_offset + 1]
            else:
                _offset += 1 # 不是乘或除一律跳过
                if text[_offset] == ")": # 括号结束 要跳出
                    break
                continue
            prepop.append(_offset - 1) # 已经参与了运算的元素
            prepop.append(_offset)
            _offset += 1
        text = [_ for index, _ in enumerate(text) if index not in prepop] # 去掉参与了运算的元素
        prepop = []
        _offset = offset # 遍历起始位置_offset重置为offset 
        while _offset >= offset and _offset < len(text) - 1: # 处理加减
            if _offset in prepop: continue
            if text[_offset] == "+":
                text[_offset + 1] = text[_offset - 1] + text[_offset + 1]
            elif text[_offset] == "-":
                text[_offset + 1] = text[_offset - 1] - text[_offset + 1]
            else:
                _offset += 1
                if text[_offset] == ")": # 右括号 说明运算结束
                    offset = _offset - len(prepop) # offset位置就是右括号
                    break
                continue
            prepop.append(_offset - 1)
            prepop.append(_offset)
            _offset += 1
        text = [_ for index, _ in enumerate(text) if index not in prepop]
        if len(text) == 1:
            return text[0] # 最终结果 直接返回结果
        else:
            # 还没运算完  返回上一级
            _ = text.pop(offset) # offset 是右括号位置 删除右括号
            _ = text.pop(offset - 1 - 1) # 删除左括号
            return text
        
while True:
    try:
        texts = input()
    except:
        break
    if texts == "":
        break
    texts = convert(texts)
    res = calc(texts, 0)
    print(res)