开发者

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

开发者 https://www.devze.com 2023-01-17 10:43 出处:网络 作者: AnjaVon
目录题目思路:栈【计算器】JavaC++Rust总结题目 题目要求 思路:栈【计算器】
目录
  • 题目
    • 思路:栈【计算器】
  • Java
    • C++
      • Rust
        • 总结

          题目

          题目要求

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

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

          思路:栈【计算器】

          • 和计算器原理类似,分别用两个栈存操http://www.devze.com作数和操作符,然后到)就开始运算前面的内容,括号里运算都相同所以还是比较简单的。
          • 要注意字母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 开发者_Go入门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 {
                          js            tmp =JvcZk bx & by;
                           js       }
                                  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)javascript

          总结

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

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

          0

          精彩评论

          暂无评论...
          验证码 换一张
          取 消

          关注公众号