//-------------------------------------------------------------------
// File   :match_parentheses.C
// Author :Alicia Thorsen
// Course :CS1129
//
// Uses a stack to match parentheses in an expression.
//-------------------------------------------------------------------

#include <stack>
#include <iostream>
#include <fstream>
using namespace std;

const string FILENAME = "input.txt";
const string PARENTHESES = "(){}[]";

bool isOpen(char);
bool isClose(char);
bool isMatch(char, char);

int main() {
  ifstream in(FILENAME.c_str());
  string expr;
  bool balanced;

  if (!in) {
    cout << "Input file " << FILENAME << " not found. Aborting." << endl;
    exit(1);
  }
  getline(in, expr);

  while (!in.eof()) {
    stack<char> s;
    balanced = true;

    // Parse each character in the expression.
    for (int i = 0; i < expr.length() && balanced; ++i) {

      // Push open parentheses on the stack.
      if (isOpen(expr[i]))
        s.push(expr[i]);

      // Pop matching open parentheses off the stack.
      else if (isClose(expr[i])) { 
        if (isMatch(s.top(), expr[i]))
          s.pop();
        // If close does not match open, expression not balanced.
        else 
          balanced = false;
      }
    }

    if (s.empty() && balanced) 
      cout << expr << "\nBalanced\n" << endl;
    else
      cout << expr << "\nNOT Balanced\n" << endl;

    getline(in, expr);
  }
  return 0;
}

bool isOpen(char c) {
  for (int i = 0; i < PARENTHESES.length() - 1; i += 2)
    if (c == PARENTHESES[i])
      return true;
  return false;
}

bool isClose(char c) {
  for (int i = 1; i < PARENTHESES.length(); i += 2)
    if (c == PARENTHESES[i])
      return true;
  return false;
}

bool isMatch(char open, char close) {
  for (int i = 0; i < PARENTHESES.length() - 1; i += 2)
    if (open == PARENTHESES[i] && close == PARENTHESES[i + 1])
      return true;
  return false;
}