class Solution {
  public boolean isValid(String s) {
    //聲明匹配詞典
    Map<Character, Character> map = new HashMap<>();
    map.put(')', '(');
    map.put(']', '[');
    map.put('}', '{');
    //創(chuàng)建棧
    Stack<Character> stack = new Stack<>();
    for (char ch : s.toCharArray()) {
      //開分隔符入棧
      if (ch == '(' || ch == '[' || ch == '{') {
        stack.push(ch);
      }
      //出棧并且棧非空進行匹配
      else if (stack.isEmpty() || stack.pop() != map.get(ch)){
        return false;
      }
    }
    //如果棧非空則括號匹配錯誤
    return stack.isEmpty();
  }
}

//括號匹配算法
    public void pipei()throws Exception{
      char temp,ch;
      int match;  //記錄匹配結(jié)果
      BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
      ch=(char) br.read();    //輸入一個字符
      while(ch!='0'){
        if(getTop()==-1){
          push(ch);
        }else{
          temp=pop();    //取出棧頂元素
          match=0;  //判斷是否匹配（默認(rèn)不匹配）
          if(temp=='('&&ch==')')
            match=1;
          if(temp=='['&&ch==']')
            match=1;
          if(temp=='{'&&ch=='}')
            match=1;
          if(temp=='<'&&ch=='>')
            match=1;
          if(match==0){  //如果不匹配
            push(temp);  //將原棧頂元素重新入棧
            push(ch);  //將輸入的括號字符入棧
          }
        }
        ch=(char) br.read();  //輸入下一個字符
      }
      if(isEmpty()){
        System.out.println("輸入的括號完全匹配！");
      }else{
        System.out.println("輸入的括號不匹配，請檢查！");
      }
    }

package com.cn.datastruct;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Scanner;

public class KuoHaoPiPei {
  static class Stack{
    char[] data; //存放數(shù)據(jù)
    int MaxSize;  //最大容量
    int top;    //棧頂指針
    //構(gòu)造方法
    public Stack(int MaxSize){
      this.MaxSize=MaxSize;
      data = new char[MaxSize];
      top = -1;
    }

    public int getMaxSize() {
      return MaxSize;
    }

    public int getTop() {
      return top;
    }

    public boolean isEmpty(){
      return top==-1;
    }
    
    public boolean isFull(){
      return top+1==MaxSize;
    }
    //入棧
    public boolean push(char data){
      if(isFull()){
        System.out.println("棧已滿!");
        return false;
      }
      this.data[++top]=data;
      return true;
    }
    //出棧
    public char pop() throws Exception{
      if(isEmpty()){
        throw new Exception("棧已空！");
      }
      return this.data[top--];
    }    
    //獲得棧頂元素
    public char peek(){
      return this.data[getTop()];
    }
    
    //括號匹配算法
    public void pipei()throws Exception{
      char temp,ch;
      int match;  //記錄匹配結(jié)果
      BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
      ch=(char) br.read();    //輸入一個字符
      while(ch!='0'){
        if(getTop()==-1){
          push(ch);
        }else{
          temp=pop();    //取出棧頂元素
          match=0;  //判斷是否匹配（默認(rèn)不匹配）
          if(temp=='('&&ch==')')
            match=1;
          if(temp=='['&&ch==']')
            match=1;
          if(temp=='{'&&ch=='}')
            match=1;
          if(temp=='<'&&ch=='>')
            match=1;
          if(match==0){  //如果不匹配
            push(temp);  //將原棧頂元素重新入棧
            push(ch);  //將輸入的括號字符入棧
          }
        }
        ch=(char) br.read();  //輸入下一個字符
      }
      if(isEmpty()){
        System.out.println("輸入的括號完全匹配！");
      }else{
        System.out.println("輸入的括號不匹配，請檢查！");
      }
    }
  }
  
  public static void main(String[] args) throws Exception {
    String go;
    Scanner input = new Scanner(System.in);
    Stack stack = new Stack(20);
    System.out.println("括號匹配問題！");
    do{
      System.out.println("請輸入一組括號的組合，以0表示結(jié)束。支持的括號包括：{},(),[],<>。");
      stack.pipei();    //匹配算法
      System.out.print("\n繼續(xù)匹配嗎（y/n）?");
      go=input.next();
    }while(go.equalsIgnoreCase("y"));
    System.out.println("匹配結(jié)束！");
  }

}

#include <cstdio>
#include <iostream>
using namespace std;
 
#define MAXSIZE 20
 
typedef struct {
	char *base;
	char *top;
	int stacksize;
}SqStack;
 
void InitStack(SqStack &S)
{
	S.base = (char *)malloc( MAXSIZE * sizeof(char) );
	if(S.base == NULL)	exit(-2);
	S.top = S.base;
	S.stacksize = MAXSIZE;
}
 
void GetTop(SqStack S, char &e)
{
	if(S.top == S.base)
		return;
	e = *(S.top - 1);
}
 
void Push(SqStack &S, char e)							//	不考慮棧滿
{
	*S.top++ = e;
}
 
void Pop(SqStack &S, char &e)
{
	if(S.top == S.base)
		return;
	S.top--;
	e = *S.top;
}
 
bool Match(char c, SqStack &my_stack, bool &tag)
{
	char e;
	Pop(my_stack, e);
	if ( c != e ) {
		tag = false;
		free(my_stack.base);
		return false;									//	match fail
	}
	return true;										//	match success
}
 
void Correct(char *expr, bool &tag)
{
	tag = true;	
	SqStack my_stack;
	InitStack (my_stack);
	for( int i = 0; expr[i] != '\0'; i++ ) {
		char c = expr[i];
		switch(c) {
			
		case '{' : case '[' : case '(' :
			Push (my_stack, c); break;
			
		case '}' : 
			if( Match('{', my_stack, tag) == false )	//	match fail
				return;
			break;
			
		case ']' : 
			if( Match('[', my_stack, tag) == false )	//	match fail
				return;
			break;
			
		case ')' : 
			if( Match('(', my_stack, tag) == false )	//	match fail
				return;
			break;
			
		default :
			break;										//	其它字符
		}
	}
	if(my_stack.top != my_stack.base)					// e.g.: "[r"
		tag = false;
	free(my_stack.base);
}
 
int main(void)
{
	//	freopen("cin.txt", "r", stdin);
	char my_expr[MAXSIZE];
	while(cin >> my_expr) {
		bool tag = true;
		Correct( my_expr, tag);
		tag ? printf("匹配成功\n") : printf("匹配失敗\n");
	}
	
	return 0;
}