学步园

一、要求：

判断一个字符串中的小括号是否匹配。例如，字符串“（（（））（））”中的小括号匹配，而“）（）”中的小括号不匹配。如果匹配则提示匹配，如果不匹配则提示第一个不匹配的括号的位置。

 

二、 效果：

 

三、思路：

得到字符串，从头开始，一个一个字符判断。

（1） 如果是左括号则压入栈中。

（2） 如果是右括号，则将一个左括号从栈中弹出，匹配一对。若此时栈中无元素，那么这个右括号没有匹配的左括号。

最后，如果栈不为空，则有左括号没有匹配。

 

四、核心代码：

for(i = 0; i < brackets.length(); i++) {
        if(brackets[i] == '(') {
        //1.left bracket
            bracketStack.push('(');
            if(bracketStack.size() == 1) {
                bottom = i;
            }
        }else if (brackets[i] == ')') {
        //2.right bracket
            if(!bracketStack.empty()) {
                tmp = bracketStack.top();
                bracketStack.pop();
            } else {
                res = nMatch;
                //move to wrong position
                i++;
                break;
            }
        }
        //ingore non bracket
    }

 

 

五、所有代码

:

 

//BracketMatch.cpp
//judge a string whether is brackets match['(' and ')'] string,
//while not match,return first position
//powered by alan
//2010.10.14

#include <iostream>
#include <string>
#include <stack>
using namespace std;
int main() {
    //define data
    string brackets = "";
    stack<char> bracketStack;
    char tmp;
    enum Res{matched,nMatch}res;
    res = matched;
    int bottom = 0;
    
    //get input
    cout<<"输入需要匹配的括号串"<<endl;
    cin>>brackets;
    
    //judge
    int i;
    for(i = 0; i < brackets.length(); i++) {
        if(brackets[i] == '(') {
        //1.left bracket
            bracketStack.push('(');
            if(bracketStack.size() == 1) {
                bottom = i;
            }
        }else if (brackets[i] == ')') {
        //2.right bracket
            if(!bracketStack.empty()) {
                tmp = bracketStack.top();
                bracketStack.pop();
            } else {
                res = nMatch;
                //move to wrong position
                i++;
                break;
            }
        }
        //ingore non bracket
    }
    
    //have '(' not match
    if(!bracketStack.empty()){
        res = nMatch;
        //get the first not match
        i = bottom + 1;
    }
    
    switch(res) {
    case matched:
        cout<<"括号字符串匹配！"<<endl;
        break;
    case nMatch:
        cout<<"第"<<i<<"个括号字符串不匹配!"<<endl;
        break;
    }
    
    return 0;
}