0020. 有效的括号 Valid Parentheses

问题描述

这个问题使用栈来解决, 思路有两种:

• 遇到左侧的括号, 就把它入栈; 遇到右侧括号, 就将栈顶元素出栈, 并比对它们是否成对
• 遇到左侧的括号, 就把与它对应的右侧括号入栈; 遇到右侧括号, 就将栈顶元素出栈, 并判断它们是否相同

代码实现

Rust

#![allow(unused)]
fn main() {
pub fn is_valid2(s: String) -> bool {
    let mut stack = Vec::<char>::new();
    for bracket in s.chars() {
        match bracket {
            // 先匹配左侧的括号, 并把与之成对的右侧括号入栈.
            '(' => stack.push(')'),
            '[' => stack.push(']'),
            '{' => stack.push('}'),
            // 如果遇到右侧括号, 就把它与栈顶元素比较, 看是否相同.
            // 使用 match-guard
            ')' | ']' | '}' if Some(bracket) != stack.pop() => return false,
            _ => (),
        }
    }

    stack.is_empty()
}
}

C++

bool isValid2(std::string s) {
  std::stack<char> stack;

  for (char c : s) {
    // 先匹配左侧的括号, 并把与之成对的右侧括号入栈.
    if (c == '(') {
      stack.push(')');
    } else if (c == '[') {
      stack.push(']');
    } else if (c == '{') {
      stack.push('}');
    } else if (stack.empty()) {
      return false;
    } else {
      // 如果遇到右侧括号, 就把它与栈顶元素比较, 看是否相同.
      char old_c = stack.top();
      stack.pop();
      if (old_c != c) {
        return false;
      }
    }
  }

  return stack.empty();
}