736. Lisp 语法解析 : DFS 模拟题

这篇具有很好参考价值的文章主要介绍了736. Lisp 语法解析 : DFS 模拟题。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

题目描述

这是 LeetCode 上的 736. Lisp 语法解析 ,难度为 困难

Tag : 「DFS」、「模拟」、「哈希表」

给你一个类似 Lisp 语句的字符串表达式 expression,求出其计算结果。

表达式语法如下所示:

  • 表达式可以为整数, let 表达式, add 表达式, mult 表达式,或赋值的变量。表达式的结果总是一个整数。
  • (整数可以是正整数、负整数、 )
  • let 表达式采用  "(let v1 e1 v2 e2 ... vn en expr)" 的形式,其中  let 总是以字符串  "let"来表示,接下来会跟随一对或多对交替的变量和表达式,也就是说,第一个变量  v1被分配为表达式  e1 的值,第二个变量  v2 被分配为表达式  e2 的值,依次类推;最终 let 表达式的值为  expr 表达式的值。
  • add 表达式表示为  "(add e1 e2)" ,其中  add 总是以字符串  "add" 来表示,该表达式总是包含两个表达式 e1e2 ,最终结果是  e1 表达式的值与  e2 表达式的值之 和 。
  • mult 表达式表示为  "(mult e1 e2)" ,其中  mult 总是以字符串 "mult" 表示,该表达式总是包含两个表达式 e1、e2,最终结果是  e1 表达式的值与  e2 表达式的值之 积 。
  • 在该题目中,变量名以小写字符开始,之后跟随 个或多个小写字符或数字。为了方便, "add""let""mult" 会被定义为 `"关键字" ,不会用作变量名。
  • 最后,要说一下作用域的概念。计算变量名所对应的表达式时,在计算上下文中,首先检查最内层作用域(按括号计),然后按顺序依次检查外部作用域。测试用例中每一个表达式都是合法的。有关作用域的更多详细信息,请参阅示例。

示例 1:

输入:expression = "(let x 2 (mult x (let x 3 y 4 (add x y))))" 输出:14 解释: 计算表达式 (add x y), 在检查变量 x 值时, 在变量的上下文中由最内层作用域依次向外检查。 首先找到 x = 3, 所以此处的 x 值是 3 。 示例 2:

输入:expression = "(let x 3 x 2 x)"

输出:2

解释:let 语句中的赋值运算按顺序处理即可。

示例 3:

输入:expression = "(let x 1 y 2 x (add x y) (add x y))"

输出:5

解释:
第一个 (add x y) 计算结果是 3,并且将此值赋给了 x 。 
第二个 (add x y) 计算结果是 3 + 2 = 5 。

提示:

  • exprssion 中不含前导和尾随空格
  • expressoin 中的不同部分( token)之间用单个空格进行分隔
  • 答案和所有中间计算结果都符合 32-bit 整数范围

DFS 模拟

今天身体不舒服,不写太详细,题目不难,大家结合代码看吧。

设计函数 int dfs(int l, int r, Map<String, Integer> map) 函数,代表计算 的结果,答案为 dfs(0,n-1,map),其中 为字符串的长度。

根据传入的 是否为表达式分情况讨论:

  • ,说明是表达式,此时从 开始往后取,取到空格为止(假设位置为 idx),从而得到操作 op(其中 opletaddmult 三者之一),此时 op 对应参数为 ,也就是需要跳过位置 (即跳过 op 对应的 ) 符号);

    再根据 op 为何种操作进一步处理,我们设计一个「传入左端点找右端点」的函数 int getRight(int left, int end),含义为从 left 出发,一直往右找(不超过 end),直到取得合法的「子表达式」或「对应的值」。

    // 对于 getRight 函数作用,给大家举个 🌰 理解吧,其实就是从 left 出发,找到合法的「子表达式」或「值」为止

    // (let x 2 (mult x (let x 3 y 4 (add x y))))
    //          a                               b
    // 传入 a 返回 b,代表 [a, b) 表达式为 (mult x (let x 3 y 4 (add x y)))

    // (let x 2 (mult x (let x 3 y 4 (add x y))))
    //      ab
    // 传入 a 返回 b,代表 [a, b) 表达式为 x
  • 否则 不是表达式,通过判断 是否有被哈希表记录来得知结果:若在哈希表中有记录,结果为哈希表中的映射值,否则结果为本身所代表的数值。

需要注意,根据「作用域」的定义,我们不能使用全局哈希表,而要在每一层递归时,传入 clone 出来的 map

代码:

class Solution {
    char[] cs;
    String s;
    public int evaluate(String _s) {
        s = _s;
        cs = s.toCharArray();
        return dfs(0, cs.length - 1new HashMap<>());
    }
    int dfs(int l, int r, Map<String, Integer> map) {
        if (cs[l] == '(') {
            int idx = l;
            while (cs[idx] != ' ') idx++;
            String op = s.substring(l + 1, idx);
            r--; // 判别为 "(let"、"(add" 或 "(mult" 后,跳过对应的 ")"
            if (op.equals("let")) {
                for (int i = idx + 1; i <= r; ) {
                    int j = getRight(i, r);
                    String key = s.substring(i, j);
                    if (j >= r) return dfs(i, j - 1new HashMap<>(map));
                    j++; i = j;
                    j = getRight(i, r);
                    int value = dfs(i, j - 1new HashMap<>(map));
                    map.put(key, value);
                    i = j + 1;
                }
                return -1// never
            } else if (op.equals("add")) {
                int j = getRight(idx + 1, r);
                int a = dfs(idx + 1, j - 1new HashMap<>(map)), b = dfs(j + 1, r, new HashMap<>(map));
                return a + b;
            } else {
                int j = getRight(idx + 1, r);
                int a = dfs(idx + 1, j - 1new HashMap<>(map)), b = dfs(j + 1, r, new HashMap<>(map));
                return a * b;
            }
        } else {
            String cur = s.substring(l, r + 1);
            if (map.containsKey(cur)) return map.get(cur);
            return Integer.parseInt(cur);
        }
    }
    int getRight(int left, int end) {
        int right = left, score = 0;
        while (right <= end) {
            if (cs[right] == '(') {
                score++; right++;
            } else if (cs[right] == ')') {
                score--; right++;
            } else if (cs[right] == ' ') {
                if (score == 0break;
                right++;
            } else {
                right++;
            }
        }
        return right;
    }
}
  • 时间复杂度:除对表达式进行递归划分以外,还存在对 map 的每层拷贝操作,复杂度为
  • 空间复杂度:

最后

这是我们「刷穿 LeetCode」系列文章的第 No.736 篇,系列开始于 2021/01/01,截止于起始日 LeetCode 上共有 1916 道题目,部分是有锁题,我们将先把所有不带锁的题目刷完。

在这个系列文章里面,除了讲解解题思路以外,还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码,我建立了相关的仓库:https://github.com/SharingSource/LogicStack-LeetCode 。

在仓库地址里,你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。

更多更全更热门的「笔试/面试」相关资料可访问排版精美的 合集新基地 🎉🎉

本文由 mdnice 多平台发布文章来源地址https://www.toymoban.com/news/detail-438813.html

到了这里,关于736. Lisp 语法解析 : DFS 模拟题的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • pta模拟题——7-34 刮刮彩票

    “刮刮彩票”是一款网络游戏里面的一个小游戏。如图所示: 每次游戏玩家会拿到一张彩票,上面会有 9 个数字,分别为数字 1 到数字 9,数字各不重复,并以 3×3 的“九宫格”形式排布在彩票上。 在游戏开始时能看见一个位置上的数字,其他位置上的数字均不可见。你可

    2024年02月04日
    浏览(47)
  • 蓝桥杯嵌入式--实战模拟题

    在蓝桥杯省赛举办之前,学校组织了一场模拟赛,基于第十三届的省赛题,但是难度略高于省赛,这篇博客记录一下解题的过程,其思路可供大家参考。 详细工程目前先联系我获取。 花个十几分钟把题目好好理解一下,然后先整理出一个大体的运行原理。很容易我们就想到

    2023年04月10日
    浏览(40)
  • 软考高项:信息网络安全模拟题

    280、在TCP/IP的体系架构中,ARP协议位于(),它的作用是()。 A.网络层将MAC地址解析为IP地址 B.链路层将MAC地址解析为IP地址 C.网络层将IP地址解析为MAC地址 D.链路层将lP地址解析为MAC地址 正确答案:D 解析:在TCP/IP的体系架构中,ARP协议位于链路层,它的作用是将IP地址解析为MAC地址

    2024年02月13日
    浏览(43)
  • Vj程序设计复杂模拟题训练

    飞飞很喜欢打牌,他决定苦练牌技,终成赌神! 飞飞有  A  ×  B  张扑克牌。每张扑克牌有一个大小(整数,记为 a,范围区间是 0 到  A  - 1)和一个花色(整数,记为 b,范围区间是 0 到  B  - 1。 扑克牌是互异的,也就是独一无二的,也就是说没有两张牌大小和花

    2023年04月19日
    浏览(50)
  • csp-j/s模拟题详细题解

    题目描述 一天小理买了N个容量可以认为是无限大的瓶子,开始时每个瓶子里有1升水。接着小理发现瓶子实在太多了,于是他决定保留不超过K个瓶子,每次他选择两个当前含水量相同的瓶子合并。(即把一个瓶子的水全部倒进另一个里然后把空瓶丢弃) (注:不能丢弃有水

    2024年02月10日
    浏览(36)
  • 软考高项:信息网络安全知识模拟题

    620、以下哪个场景属于身份鉴别过程()。 A.用户依照提示输入用户名、口令和短信验证码,成功登录该应用。 B.用户在网络上共享了的一份加密的pdf文档,以阻止其他人下载查看文档中的内容。 C.用户给自己编写的文档加上水印。 D.用户在网上下载了一份带水印的文档,去掉

    2024年02月05日
    浏览(41)
  • 国家信息安全水平考试NISP一级模拟题

    1.   下列关于用户口令说法错误的是 (   ) 。 A.   口令不能设置为空 B.   口令长度越长,   安全性越高 C.   复杂口令安全性足够高,不需要定期修改 D.   口令认证是最常见的认证机制 正确答案:   C 2.   下列关于木马病毒的特性,   不正确的是 (   ) 。 A.   隐蔽

    2023年04月08日
    浏览(50)
  • 网络安全模拟题----软考高项的走过来

    1、某公司技术人员利于自己的技术入侵了某电商数据库,将其中的用户数据下载后在暗网中进行售卖,该行为的处置最适用的是以下那部法律?(  ) A.刑法    B.网络安全法     C.电子签名法     D.劳动法 正确答案:A     解析:入侵他人网站,角触犯的是刑法,不属于

    2024年02月10日
    浏览(41)
  • 信息网络安全模拟题----软考高项的走过来

    101、通过“计算机管理”来清除时间日志也可以达到清除痕迹的目的,具体操作是() A.禁用“event system”服务        B.禁用“net logon”服务 C.禁用“event log”服务      D.禁用“secondary logon”服务 正确答案:C     解析:通过“计算机管理”来清除时间日志也可以达到清

    2024年02月08日
    浏览(46)
  • 蓝桥杯web开发-5道模拟题让你信心满满

    💖 作者简介:大家好,我是阿牛,全栈领域新星创作者。😜 📝 个人主页:馆主阿牛🔥 🎉 支持我:点赞👍+收藏⭐️+留言📝 📣 系列专栏:硬泡 javascript🍁 💬格言:迄今所有人生都大写着失败,但不妨碍我继续向前!🔥 前些天发现了一个比较好的人工智能学习网站,

    2023年04月09日
    浏览(87)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包