乐趣区

关于python:224-基本计算器│leetcode

jiezi 
 实现一个根本的计算器来计算一个简略的字符串表达式 s 的值。示例 1：输出：s = "1 + 1"
输入：2
示例 2：输出：s = "2-1 + 2"
输入：3
示例 3：输出：s = "(1+(4+5+2)-3)+(6+8)"
输入：23

提醒：1. 1 <= s.length <= 3 * 105
2. s 由数字、'+'、'-'、'('、')'、和 ' ' 组成
3. s 示意一个无效的表达式

题目给出, 难度为艰难.

刚审完题, 第一感觉还是挺简略的嘛, 只有加减法, 那括号就没用了嘛. 提前说一下, 括号没用这句话是谬误的.

一开始, 本人的思路是先把空格, 括号去掉, 而后创立两个栈, 一个寄存数字, 一个寄存符号, 而后线性循环字符串表达式, 进行响应的运算. 这里举荐一下邓俊华老师的数据结构与算法这门课程 (https://www.bilibili.com/vide…

当我写完一版, 信念满满的去提交时, 遇到了一个不能把括号省去的字符串表达式: - (3 + (4 + 5)). 原来从最开始的剖析问题我就走错了.

那么, 正片开始.

首先, 字符串表达式中的空格是有效字符, 能够去除. 创立两个栈, 一个寄存数字, 另一个寄存符号. 并且字符串表达式的最初要增加一个终止符, 这个终止符能够是除了表达式可能呈现的任意字符, 这里抉择了 $ 符号. 符号栈中同样也增加一个 $ 符号示意终止符.

s = s.replace('','') + '$'
数字栈, 符号栈 = [0], ['$']

数字栈中增加一个 0, 一是不会影响 +, - 的运算后果, 二是为了避免表达式中第一个数字是正数的状况.(血淋淋的教训呀, 万恶的 leetcode 什么题都出)

在字符串表达式中, 相加减的两个数字不肯定仅是个位数, 然而咱们又只能一个字符一个字符的读取, 所以要存储一下前一个读取字符, 如果前一个读取字符是数字, 那么就将数字栈最初一位出栈, 乘以 10 再加上以后数字. 所以须要创立一个变量 

 上一字符 = ''

如何执行运算呢? 判断符号栈中是否还存在元素, 如果存在就执行循环. 为什么不能只循环一遍字符串表达式呢, 这个能够在最初说.

在循环中, 如果以后字符是数字, 那么就要判断一下, 如果前一个读取的字符是数字, 那么就要将数字栈中的最初一位出栈, 乘以 10 再加上以后数字. 否则间接退出数字栈中. 而后将读取字符索引向前一位.

对了, 说到了字符串表达式的索引, 须要提前创立一个存储以后索引的变量.

if s[s_index].isnumeric():  # 是否只蕴含数字
    if 上一字符.isnumeric():  # 上一字符是数字, 要合并
        数字栈.append(数字栈.pop() * 10 + int(value))
    else:
        数字栈.append(int(value))
    s_index += 1

在循环中, 如果以后字符是符号, 问题就简单很多了. 加法减法何时计算, 括号怎么办. 设置优先级就是正解.

— + – ( ) $
  • | > | > | < | > | >
  • | > | > | < | > | >

(| < | < | < | = |
) | | | | |
$ | < | < | < | | =

如果以后字符是符号, 那么判断符号栈中最初一位与以后字符的优先级关系, 如果以后字符优先级高, 也就是 <. 符号栈中最初一位不能计算, 以后符号退出符号栈.

如果以后字符优先级与符号栈中最初一位符号雷同, 那么在优先级表中, 只有 $ 与 $ 本身和 ( 与 ) 之间的优先级是相等的. $ 与本身相遇阐明完结了, ( 与 ) 相遇阐明这一对括号间仅有一个数字, 没有任何符号了, 这时括号就失去作用了. 那么这时的操作就是将符号栈的最初一位出栈.

以上两条分支执行后都须要将字符索引向前一位.

如果以后字符优先级低, 也就是 >, 阐明栈中的符号能够计算了. 首先将符号栈中最初一位出栈, 数字栈中最初两位出栈, 留神, 数字栈中, 第一个出栈的数字在计算是应该在符号前. 而后进行计算后将后果退出到数字栈中. 这里不须要向前挪动字符索引, 因为可能有符号栈中多个字符优先级都高于以后字符.

循环完结后, 在数字栈中可能存在两个元素, 其中第一个是最开始增加的 0, 在不是非凡状况时, 这个元素 0 将不会被应用到. 无论如何, 数字栈中的最初一位就是表达式后果.

class Solution:
    def calculate(self, s: str) -> int:
        s = s.replace('','') + '$'
        数字栈, 符号栈, 上一字符, s_index = [0], ['$'], '', 0
        符号优先级表 = {"+": {"+": '>', '-': '>', '(': '<', ')': '>', '$': '>'},
            "-": {"+": '>', '-': '>', '(': '<', ')': '>', '$': '>'},
            "(": {"+": '<', '-': '<', '(': '<', ')': '=', '$': ''},")": {"+":' ','-':' ','(':' ',')':' ','$':' '},"$": {"+":'<','-':'<','(':'<',')':' ','$':'='}
        }
        while len(符号栈) >= 1:
            value = s[s_index]
            if s[s_index].isnumeric():  # 是否只蕴含数字
                if 上一字符.isnumeric():  # 上一字符是数字, 要合并
                    数字栈.append(数字栈.pop() * 10 + int(value))
                else:
                    数字栈.append(int(value))
                s_index += 1
            else:
                if 符号优先级表 [符号栈 [-1]][value] == '<':  # 栈中的比以后低, 以后符号进栈
                    符号栈.append(value)
                    s_index += 1
                elif 符号优先级表 [符号栈 [-1]][value] == '=':  # 括号闭合, 或完结
                    符号栈.pop()
                    s_index += 1
                elif 符号优先级表 [符号栈 [-1]][value] == '>':  # 栈中优先级高, 可计算
                    符号, 数字 A, 数字 B = 符号栈.pop(), 数字栈.pop(), 数字栈.pop()
                    数字栈.append((数字 B - 数字 A) if 符号 == '-' else (数字 B + 数字 A))
            上一字符 = value
        return 数字栈.pop()

公众号 :「python 杂货铺」，专一于 python 语言及其相干常识。挖掘更多原创文章，期待您的关注。

退出移动版