iT邦幫忙

1

資結經典題目: 用stack 解括號配對問題

題目簡介

今天要介紹一道經典題- 括號配對問題,
輸入可能抱括圓括號 ()、方括號 []、小於大於括號 <> 和曲括號 {},
判斷括號配對是否正確

<正確的範例>

  • 空字串
  • ()[]{<>}
  • {()<>}[]
  • ((()))

<不正確的範例>

  • (]
  • ([)]
  • ())
  • <<

題目資源

這是一道很經典的問題,網上許多OJ都有這一題:

  1. zerojude- b304: 00673 - Parentheses Balance
  2. zerojude- b838: 104北二2.括號問題
  3. zerojude- e924: pC. 括號配對
  4. LeetCode- 20. Valid Parentheses

解題思路

括號配對是一道蠻適合用stack來解的問題
(stack的觀念介紹: 【小馬的資結演算法秘笈】(5) stack與queue )

讀入一個字串,當看到左括號(可能是「(」、「[」、「<」、「{」)的時候,
需要等著配對相對應的右括號,
就把左括號放進stack裡面
右括號可以把對應左括號消除

譬如我們有字串(<>)
一開始把(放進stack裡面,
第二個字看到<,那麼<配對的優先權就更高了,
變成要先配對>而不是配對),
因此括號配對滿足stack的特性 (愈後面出現的左括號愈優先配對)

最後如果stack裡面的左括號順利被右括號消除完,
才算括號配對成功

程式碼範例(解e924: pC. 括號配對)

#include <iostream>
#include <string>
using namespace std;

class Stack{
private:
    const int max_sz; //預設stack的最大容量
    int currunt_sz = 0; //目前Stack裡有幾個元素
    char *arr;
public:
    Stack():max_sz(500){arr = new char[max_sz];};
    Stack(int sz):max_sz(sz){arr = new char[max_sz];};
    void push(char data);
    void pop();
    char top();
    int size();
};

void Stack::push(char data){
    arr[currunt_sz]=data;
    currunt_sz++;
}


void Stack::pop(){
    currunt_sz--;
}

char Stack::top(){
    return currunt_sz>0?arr[currunt_sz-1]:0;
}

int Stack::size(){
    return currunt_sz;
}

bool cheakValidParentheses(const string& s){
    Stack stack(1000);
    for (auto c : s) {
        if(c=='(' || c=='['|| c=='<' || c=='{'){
            stack.push(c);
        }
        else{
            switch(c){
                case ')':
                    if(stack.size() && stack.top()=='('){
                        stack.pop();
                        break;
                    }
                    return false;
                case ']':
                    if(stack.size() && stack.top()=='['){
                        stack.pop();
                        break;
                    }
                    return false;
                case '>':
                    if(stack.size() && stack.top()=='<'){
                        stack.pop();
                        break;
                    }
                    return false;
                case '}':
                    if(stack.size() && stack.top()=='{'){
                        stack.pop();
                        break;
                    }
                    return false;
            }
        }
    }
    return stack.size()==0;
    
}
int main()
{
    int t;
    string test;
    cin >> t;
    getline(cin, test); //吃掉第一行的換行字符
    for(int i=0; i<t;i++){
        getline(cin, test); //選擇用getline讀字串是因為怕測資有空字串
        std::cout << (cheakValidParentheses(test)?'Y':'N') << std::endl;
    }
    return 0;
}

尚未有邦友留言

立即登入留言