Java C++刷题leetcode1106解析布尔表达式

目录
  • 题目
    • 思路:栈【计算器】
  • Java
  • C++
  • Rust
  • 总结

题目

题目要求

思路:栈【计算器】

  • 和计算器原理类似,分别用两个栈存操作数和操作符,然后到)就开始运算前面的内容,括号里运算都相同所以还是比较简单的。
  • 要注意字母t、f和布尔值truefalse的转换。

Java

class Solution {
    public boolean parseBoolExpr(String expression) {
        Deque<Character> tfs = new ArrayDeque<>(), opts = new ArrayDeque<>();
        for (char c : expression.toCharArray()) {
            if (c == ',')
                continue;
            else if (c == 't' || c == 'f' || c == '(')
                tfs.addLast(c);
            else if (c == '|' || c == '&' || c == '!')
                opts.addLast(c);
            else if (c == ')') {
                char op = opts.pollLast(), cur = ' ';
                while (!tfs.isEmpty() && tfs.peekLast() != '(') {
                    char top = tfs.pollLast();
                    cur = cur == ' ' ? top : calBool(top, cur, op);
                }
                if (op == '!')
                    cur = cur == 't' ? 'f' : 't';
                tfs.pollLast();
                tfs.addLast(cur);
            }
        }
        return tfs.peekLast() == 't';
    }
    char calBool(char cx, char cy, char op) {
        boolean bx = cx == 't', by = cy == 't';
        boolean res = op == '|' ? bx | by : bx & by;
        return res ? 't' : 'f';
    }
}
  • 时间复杂度:O(n)
  • 空间复杂度:O(n)

C++

class Solution {
public:
    bool parseBoolExpr(string expression) {
        stack<char> tfs, opts;
        for (auto c : expression) {
            if (c == ',')
                continue;
            else if (c == 't' || c == 'f' || c == '(')
                tfs.push(c);
            else if (c == '|' || c == '&' || c == '!')
                opts.push(c);
            else if (c == ')') {
                char op = opts.top(), cur = ' ';
                opts.pop();
                while (!tfs.empty() && tfs.top() != '(') {
                    char top = tfs.top();
                    tfs.pop();
                    cur = cur == ' ' ? top : calBool(top, cur, op);
                }
                if (op == '!')
                    cur = cur == 't' ? 'f' : 't';
                tfs.pop();
                tfs.push(cur);
            }
        }
        return tfs.top() == 't';
    }
    char calBool(char cx, char cy, char op) {
        bool bx = cx == 't', by = cy == 't';
        bool res = op == '|' ? bx | by : bx & by;
        return res ? 't' : 'f';
    }
};
  • 时间复杂度:O(n)
  • 空间复杂度:O(n)

Rust

impl Solution {
    pub fn parse_bool_expr(expression: String) -> bool {
        let (mut tfs, mut opts) = (vec![], vec![]);
        for c in expression.chars() {
            if c == 't' || c == 'f' || c == '(' {
                tfs.push(c);
            }
            else if c == '|' || c == '&' || c == '!' {
                opts.push(c);
            }
            else if c == ')' {
                let op = opts.pop().unwrap();
                let mut cur = 'e';
                while !tfs.is_empty() && tfs[tfs.len() - 1] != '(' {
                    let top = tfs.pop().unwrap();
                    if cur == 'e' {
                        cur = top;
                    }
                    else { // fn calBool()
                        let (bx, by, mut tmp) = (top == 't', cur == 't', false);
                        if op == '|' {
                            tmp = bx | by;
                        }
                        else {
                            tmp = bx & by;
                        }
                        if tmp {
                            cur = 't';
                        }
                        else {
                            cur = 'f';
                        }
                    }
                }
                if op == '!' { // 非
                    if cur == 't' {
                        cur = 'f';
                    }
                    else {
                        cur = 't';
                    }
                }
                tfs.pop();
                tfs.push(cur);
            }
        }
        tfs.pop().unwrap() == 't'
    }
}
  • 时间复杂度:O(n)
  • 空间复杂度:O(n)

总结

  • 像是数据结构里学栈时举的计算器的例子,就循着这个思路感觉不算困难题。
  • 当然也可以递归或者只用一个栈,整体思路其实就是巧妙一点的模拟。

以上就是Java C++刷题leetcode1106解析布尔表达式的详细内容,更多关于Java C++解析布尔表达式的资料请关注我们其它相关文章!

(0)

相关推荐

  • Java C++题解leetcode915分割数组示例

    目录 题目要求 思路一:两次遍历 Java C++ Rust 思路二:一次遍历 Java C++ Rust 题目要求 题目链接 思路一:两次遍历 题目的意思也就是左半边数组的最大值小于等于右半边数组的最小值,那么就找这个分界点就好: 首先从后向前遍历,找[i,n−1]里最小的值: 然后从前向后遍历,找[0,i]里最大的值: 然后找满足max[i]<=min[i+1]的分割点i: 可以将2.3两步结合为一步完成,由于iii从前向后不断增大,所以用后面(较大)的值覆盖更新之前的值. 找到分界点的索引

  • Java C++题解leetcode 1684统计一致字符串的数目示例

    目录 题目 思路:模拟 Java C++ Rust 题目 题目要求 思路:模拟 用一个哈希表记录可出现的字母,然后逐一遍历每个单词每个字母,符合条件则结果加一. Java class Solution { public int countConsistentStrings(String allowed, String[] words) { boolean[] hash = new boolean[26]; for (var a : allowed.toCharArray()) hash[a -

  • Java C++ leetcode面试零矩阵

    目录 题目要求 思路:模拟 Java C++ Rust 总结 题目要求 思路:模拟 定义两个数组分别记录每行or每列中为0的元素: 0所在的行列清零也就意味着元素所在行or列有0则置零[废话连篇]: 所以一次遍历找出有0的行列,一次遍历根据其将相应元素置零. Java class Solution { public void setZeroes(int[][] matrix) { int n = matrix.length, m = matrix[0].length; boolean[] row

  • Java C++题解leetcode816模糊坐标示例

    目录 题目 思路:枚举 Java C++ Rust 总结 题目 题目要求 思路:枚举 既然要输出每种可能了,那必然不能“偷懒”,就暴力枚举咯: 在每个间隔处添加逗号: 定义函数decPnt(sta, end)分别列举逗号左右两边的数能构成的可能性: 同样在每个间隔添加小数点: 注意两种不合法的结构——前导0和后缀0: 不要忘记无小数点的整数版本, 分别组合两边的不同可能性,根据要求各式加入答案. Java class Solution { String str; public List<Stri

  • 如何在Intellij中安装LeetCode刷题插件方便Java刷题

    一.安装 在 IDEA(2019)的 setting 的 Plugins 的 Marketplace 中搜索 leetcode,即可以找到该插件,安装完成了,重启即可. 二.配置 1.重启完成后,第一次使用的时候,需要一些基本的配制,在 setting 中的 Tools 中可以找到该插件工具,为 leetcode plugin,在里面,可以选择访问的为国际的 LeetCode 还是国内的,以及何种语言,同时,输入自己账户名(LoginName)和密码(Password),则可以和自己帐号关联起来

  • java算法Leecode刷题统计有序矩阵中的负数

    目录 leecode 1351. 统计有序矩阵中的负数 示例 1 提示 参考代码 定义一颗树 JAVA Morris leecode 1351. 统计有序矩阵中的负数 [Java 刷题打卡] 那就干吧! 这个专栏都是刷的题目都是关于二分法的,我会由浅入深.循序渐进,刷题就是这样需要连续不断的记忆--艾宾浩斯记忆法2121112.二分法的内容不多,但是都是每个程序员必备的 给你一个 m * n 的矩阵 grid,矩阵中的元素无论是按行还是按列,都以非递增顺序排列. 请你统计并返回 grid 中 负

  • IntelliJ IDEA 刷题利器 LeetCode 插件详解

    IDEA整合LeetCode插件,可以在 IDEA 本地编辑代码并且运行提交,还能关联自己的账号,非常实用. 下载安装 配置 点击File->Settings->Tools->leetcode plugin,如图: 参数说明: Custom code template: 开启使用自定义模板,否则使用默认生成格式 CodeFileName: 生成文件的名称,默认为题目标题 CodeTemplate: 生成题目代码的内容,默认为题目描述和题目代码 TemplateConstant: 模板常用

  • Java使用Jdom读取xml解析实例

    本文实例讲述了Java使用Jdom读取xml解析.分享给大家供大家参考,具体如下: package com.yanek.demo.xml.test; import java.io.File; import java.io.IOException; import java.util.Iterator; import java.util.List; import org.jdom.Document; import org.jdom.Element; import org.jdom.JDOMExcep

  • Java Web开发入门书籍实例解析(总结一)

    从事Java Web开发这一段时间来,对Java 面向对象的思想和MVC开发模式可以说已经熟悉了.我当前参与的项目使用的框架是Spring.SpringMVC.Hibernate.下面我们小编给大家整理一篇教程帮助大家学习javaweb相关知识,感兴趣的朋友可以参考下. 一.基本概念 1.1.WEB开发的相关知识 WEB,在英语中web即表示网页的意思,它用于表示Internet主机上供外界访问的资源. Internet上供外界访问的Web资源分为: 1.静态web资源(如html 页面):指w

  • Java线程安全基础概念解析

    Java线程安全初步了解.JAVA线程安全从总体上来说,是指Java对象在多线程运行环境下的一种特性,表现为常规(区别于特殊调用情况)情况下每次调用都能得到正确的逻辑结果.从本质上来说,将对象的方法行为加上了同步控制逻辑,而调用者无须做其他额外的同步控制就可以安全放心的使用对象. 1.线程安全的定义 当多个线程访问一个对象时,如果不用考虑这些线程在运行时环境下的调度和交替执行,也不需要进行额外的同步,或者在调用方进行任何其他的协调操作,调用这个对象的行为都可以获得正确的结果,那这个对象就是线程安

  • Java数组越界问题实例解析

    Java中数组初始化和OC其实是一样的,分为动态初始化和静态初始化, 动态初始化:指定长度,由系统给出初始化值 静态初始化:给出初始化值,由系统给出长度 在我们使用数组时最容易出现的就是数组越界问题,好了,这里有个简单的例子 int [][] array = {{1,2,3},{1,4}}; System.out.println(array[1][2]); 这是一个二维数组,很明显,数组越界了,控制台中会打印如下信息: Exception in thread "main" java.l

  • 使用Java进行Json数据的解析(对象数组的相互嵌套)

    这段时间我们在做一个英语翻译软件的小小小APP,涉及到了对Json数据的解析,所以特地来总结一下! 假设我们要对如下数据进行解析,其实在平时,返回的Json数据是很乱的,很难分清数据的关系,这是经过相关工具美化后的结果 { "translation": [ "爱" ], "basic": { "us-phonetic": "lʌv", "phonetic": "lʌv"

  • java的五种数据类型解析

    不知道大家对java的简单数据类型是否了解,下面针对Java的五种类型简单数据类型表示数字和字符,进行详细的讲解和分析. 一.简单数据类型初始化 在Java语言中,简单数据类型作为类的成员变量声明时自动初始化为默认值,除非显式地声明.简单数据类型为某一方法声明局部变量时不会自动地初始化而且会导致编译器扔出类似以下的错误消息"Variable x may not have been initialized.(x变量没有初始化)"表B定义了Java简单数据类型的默认值. 二.封装类 1av

  • java使用dom4j生成与解析xml文档的方法示例

    本文实例讲述了java使用dom4j生成与解析xml文档的方法.分享给大家供大家参考,具体如下: xml是一种新的数据格式,主要用于数据交换.我们所用的框架都有涉及到xml.因此解析或生成xml对程序员也是一个技术难点.这里就用dom4j来生成一个文档,需要注意的是每个xml文档只有一个根节点. package org.lxh; import java.io.File; import java.io.FileNotFoundException; import java.io.FileOutput

随机推荐

其他