Linux Access the Open Internet

20.有效的括号

给定一个只包括 ‘(‘，’)’，’{‘，’}’，’[‘，’]’ 的字符串 s ，判断字符串是否有效。有效字符串需满足：
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
每个右括号都有一个对应的相同类型的左括号。

示例 1：输入：s = “()” 输出：true

示例 2：输入：s = “()[]{}” 输出：true

示例 3：输入：s = “(]” 输出：false

分析:
1.总共有3种类型的括号, 发现合法的括号都是成对的出现的, 举几个合法的例子

(([[]]))
[()]
{}[[(())]]

2.再举几个不合法的例子

{[}]
)[{
{{(]]])

3.我们发现只要有一个右边的符号找不到和它马上匹配的左边的符号, 这个匹配都是失败的; 所以我们用栈记录最新的左边的符号, 不管是哪类左边符号都往里加入, 如果遇到了右边的符号, 马上找栈顶, 不匹配就是不合法的

class Solution {
 public:
  bool isValid(string s) {
    if (s == "") {
      return true;
    }
    stack<char> stk;
    for (auto& c : s) {
      if (c == '(' || c == '{' || c == '[') {
        stk.push(c);
      } else {
        if (stk.empty()) return false;
        char top = stk.top();
        stk.pop();
        if (c == ')' && top != '(') return false;
        if (c == '}' && top != '{') return false;
        if (c == ']' && top != '[') return false;
      }
    }
    return (stk.empty()) ? true : false;
  }
};

1106.解析布尔表达式

布尔表达式 是计算结果不是 true 就是 false 的表达式。有效的表达式需遵循以下约定：
‘t’，运算结果为 true
‘f’，运算结果为 false
‘!(subExpr)’，运算过程为对内部表达式 subExpr 进行 逻辑非（NOT）运算
‘&(subExpr1, subExpr2, …, subExprn)’，运算过程为对 2 个或以上内部表达式 subExpr1, subExpr2, …, subExprn 进行 逻辑与（AND）运算
‘|(subExpr1, subExpr2, …, subExprn)’，运算过程为对 2 个或以上内部表达式 subExpr1, subExpr2, …, subExprn 进行 逻辑或（OR）运算
给你一个以字符串形式表述的 布尔表达式 expression，返回该式的运算结果。
题目测试用例所给出的表达式均为有效的布尔表达式，遵循上述约定。

示例 1：输入：expression = “&(|(f))” 输出：false
解释：
首先，计算 |(f) —> f ，表达式变为 “&(f)” 。
接着，计算 &(f) —> f ，表达式变为 “f” 。
最后，返回 false 。
示例 2：输入：expression = “|(f,f,f,t)” 输出：true
解释：计算 (false OR false OR false OR true) ，结果为 true 。
示例 3：输入：expression = “!(&(f,t))” 输出：true
解释：
首先，计算 &(f,t) —> (false AND true) —> false —> f ，表达式变为 “!(f)” 。
接着，计算 !(f) —> NOT false —> true ，返回 true 。

分析:
1.遇到括号直接用栈处理
2.逐个扫描字符串, 如果遇到t,f,!,&,|, 左括号,直接入栈, 遇到”,” 直接忽略, 遇到右括号那么要处理一下里面的逻辑表达式, 想办法弄出来里面逻辑表达式的结果, 然后入栈, 依次出栈, 然后直到遇到左括号
3.每次处理里面的表达式的时候, 通过统计t和f的个数, 这个t和f的个数能判断出来里面的结果, 如此做法就可以处理当前内层的逻辑结果

class Solution {
 public:
  bool parseBoolExpr(string expression) {
    int len = expression.size();
    stack<char> stk;
    for (auto& c : expression) {
      if (c == '&' || c == '!' || c == 't' || c == 'f' || c == '|' || c == '(') {
        stk.push(c);
      } else if (c == ')') {
        int trueCnt = 0;
        int falseCnt = 0;
        while (stk.top() != '(') {
          char val = stk.top();
          stk.pop();
          if (val == 't') {
            ++trueCnt;
          } else if (val == 'f') {
            ++falseCnt;
          }
        }
        stk.pop();
        char op = stk.top();
        stk.pop();
        if (op == '!') {
          stk.push(falseCnt == 1 ? 't' : 'f');
        } else if (op == '&') {
          stk.push(falseCnt == 0 ? 't' : 'f');
        } else if (op == '|') {
          stk.push(trueCnt > 0 ? 't' : 'f');
        }
      }
    }
    return stk.top() == 't';
  }
};

---

转载请注明来源 goldandrabbit.github.io