判断一个只含有括号的字符串里括号是不是成对的

上周去百度商务搜索部面试,第一面问了这个题,题目大概是:

有一个字符串,里面全是大中小括号,但是所有的括号不一定都是左右匹配的,写一个程序判断这个字符串是不是所有的括号都是成对匹配的。

这个题目其实不算难,其实就是利用栈后进先出的特征来判断,如果成对就消除,到最后如果栈为空就是完全匹配的,否则就是不匹配的,面试的时候,是在纸上写的,用php实现的,用数组模拟的栈。现在回到家用c++11写一遍,代码如下


#include <iostream>
#include <stack>

using namespace std;
class Solution {
private:
  bool match(const char a, const char b) {
    switch (a) {
    case '{':
      return b == '}';
    case '(':
      return b == ')';
    case '[':
      return b == ']';
    }
    return false;
  }
  void coupleRemove(stack<char> &st, const char curr) {

    if (st.empty() || !match(st.top(), curr)) {
      st.push(curr);
      return;
    }
    if (match(st.top(), curr)) {
      st.pop();
      return;
    }
  }

public:
  bool isValid(string & s) {
    auto l = s.size();
    if (l == 0)
      return true;
    if (l == 1)
      return false;
    stack<char> st;
    for (unsigned long i = 0; i < l; i++) {
      coupleRemove(st, s[i]);
    }
    return st.size() == 0;
  }
};

int main() {
  Solution sol;
  string x = "((([)))";
  cout << sol.isValid(x) << endl;
  return 0;
}