/*
This is a free Program, You can modify or redistribute it under the terms of GNU
*Description:2013年校园招聘--小米笔试题：括号智能纠错问题
*Language: C++
*Development Environment: VC6.0
*Author: Wangzhicheng
*E-mail: 
*Date: 2013/1/6
*/
#include <iostream>
#include <cstdlib>
#include <string>
#include <list>
#include <stack>

using namespace std;

/*
*定义括号类型
*/
const char T1='(';
const char MT1=')';
const char T2='[';
const char MT2=']';
const char T3='{';
const char MT3='}';

class Match {
private:
  list<char>List;    //字符串组成的链表
  stack<char>Stack;  //字符栈
  int cnt;           //添加的括号数  
  /*
   * 判断字符c1和c2是否匹配
  */
  bool IsMatch(char c1,char c2) {
    if(c1 == T1 && c2 ==MT1) return true;
    if(c1 == MT1 && c2 ==T1) return true;
    if(c1 == T2 && c2 ==MT2) return true;
    if(c1 == MT2 && c2 ==T2) return true;
    if(c1 == T3 && c2 ==MT3) return true;
    if(c1 == MT3 && c2 ==T3) return true;
    return false;
  }
  /*
   * 返回与字符c匹配的字符
  */
  char CharMatch(char c) {
    if(c == T1) return MT1;
    if(c == MT1) return T1;
    if(c == T2) return MT2;
    if(c == MT2) return T2;
    if(c == T3) return MT3;
    if(c == MT3) return T3;
  }
public:
  Match(const string &input) {
    string::const_iterator it;
    for(it=input.begin();it!=input.end();it++) {
      List.push_back(*it);
    }
    cnt=0;
  }
  bool Correct(const string &input,string &result) {
    list<char>::iterator it;
    char c;
    bool match=true;
    for(it=List.begin();it!=List.end();it++) {
      if(*it==T1 || *it==T2 || *it==T3) Stack.push(*it);
      else {
        if(Stack.empty()==false && IsMatch(*it,Stack.top())) Stack.pop();  //已经匹配
        /*
        * 此时要么堆栈为空,要么栈顶元素和当前链表元素不匹配
        * 将与当前链表元素匹配的括号插入链表
        */
        else {
          match=false;
          c=CharMatch(*it);
          List.insert(it,c);      //在当前位置前插入
          cnt++;
        }
      }
    }
    /*
     * 此时链表中还有未匹配的括号
    */
    while(!Stack.empty()) {
      match=false;
      c=Stack.top();
      c=CharMatch(c);
      Stack.pop();
      List.insert(it,c);
      cnt++;
    }
    for(it=List.begin();it!=List.end();it++) {
      result+=*it;
    }
    return match;
  }
  int getCnt() {
    return cnt;
  }
};

void main() {
  string input;
  string result;
  cout<<"请输入只含[ ] ( ) { }的括号表达式:";
  cin>>input;
  string::const_iterator it;
  for(it=input.begin();it!=input.end();it++) {
    if(*it==T1 || *it==MT1 || *it==T2 || *it==MT2
      || *it==T3 || *it==MT3) continue;
    else {
      cerr<<"输入表达式非法!"<<endl;
      exit(1);
    }
  }
  Match match(input);
  if(!match.Correct(input,result)) {
    cerr<<"原表达式括号不匹配!"<<endl;
    cout<<"纠错后的表达式是:"<<result<<endl;
    cout<<"添加的括号数是:";
    cout<<match.getCnt()<<endl;
  }
  else cout<<"原表达式括号匹配!"<<endl;
}