Parsing Parenthesis using stack template class in C++

Question

I have a homework and its just bugging for the last 2 days, I've been doing exactly what the pseudo code and still haven't got it right yet. For example, if I put in "mike]" or "mike]123", my program will crash, due to the stack is empty...From what I observe, the program will crash when: - The stack is empty - And there is a close parenthesis PS: with the help of us2012, I can fix the crash problem. However, the result is not right. Instead of printing out "invalid", it outputs "valid"

:(

Here is the pseudo code from my professor:

def parse_parenthesis(str):
    stack = create a new empty stack of OpenParen objects
    for i from 0 to str.size() - 1:
        if str[i] is an open parenthesis
            stack.push(new OpenParen(str[i]))
        else if str[i] is not a close parenthesis:
            # str[i] is not a parenthesis of any kind, so ignore it
            continue
        # otherwise str[i] must be a close parenthesis, try to
        # match it with the most recent open paren, on the top
        # of the stack
        else if stack is empty
        return false;
        else if stack.peek() is of the same type as str[i]:
        # close properly
        stack.pop()
        else
        return false;
    if stack is not empty
        return false;
    else
        return true

and here is what I have so far:

.cpp file

bool ParenMatching(const string& s, unique_ptr<string>& output)
{
    unique_ptr<OpenParen> stack(new OpenParen);

    bool validOpen, validClose, valid;
    bool match; //haveCloseParen;
    /*string unMatch = "Unmatch";
    string unExpected = "Unexpected close paren";
    string noError = "No Error";*/

    for (size_t i = 0; i < s.length(); i++)
    {
        // check if its open parenthesis
        validOpen = stack->IsOpenParen(s[i]);
        // check if its close parenthesis
        validClose = stack->IsCloseParen(s[i]);

        // if there is open paren, push into the stack
        if(validOpen)
            stack->PushObj(s[i]);
        else if(!validClose)
        {
            continue;
        }
            else if(stack->GetObj().IsEmpty())
            valid = false;      
        else if(match = IsMatchParen(s[i], stack))
            stack->PopObj();            
        else
            valid = false;
    }

    if(!stack->GetObj().IsEmpty())
        valid = false;
    else
        valid = true;
    return valid;
}

bool IsMatchParen(const char c, const unique_ptr<OpenParen>& stack)
{   
    bool valid;
    if(c == ')' && stack->PeekObj() == '(')
        valid = true;
    else if (c == ']' && stack->PeekObj() == '[')
        valid = true;
    else if (c == '}' && stack->PeekObj() == '{')
        valid = true;
    else if (c == '>' && stack->PeekObj() == '<')
        valid = true;
    else
        valid = false;
    return valid;
}

OpenParen.cpp

// Check if its open paren
bool OpenParen::IsOpenParen(const char c)
{
    bool isOpen;
    if(c == '(' || c == '[' || c == '{' || c == '<')
        isOpen = true;
    else
        isOpen = false;
    return isOpen;
}

// check if its close paren
bool OpenParen::IsCloseParen(const char c)
{
    bool isClose;
    if(c == ')' || c == ']' || c == '}' || c == '>')
        isClose = true;
    else
        isClose = false;
    return isClose;
}

Answer 1

gcc 4.7.3: g++ -Wall -Wextra -std=c++0x parens.cpp

#include <iostream>
#include <stack>
#include <string>
#include <vector>

bool isOpen(char c) {
  return c == '(' || c == '[' || c == '{' || c == '<'; }

bool isClose(char c) {
  return c == ')' || c == ']' || c == '}' || c == '>'; }

bool isMatch(char c1, char c2) {
  return (c1 == '(' && c2 == ')')
      || (c1 == '[' && c2 == ']')
      || (c1 == '{' && c2 == '}')
      || (c1 == '<' && c2 == '>'); }

bool parse(const std::string& s) {
  std::stack<std::string::value_type> stk;

  for (std::string::size_type i = 0; i < s.size(); ++i) {
    if (isOpen(s[i])) { stk.push(s[i]); }
    else if (isClose(s[i])) {
      if (!stk.empty() && isMatch(stk.top(), s[i])) { stk.pop(); }
      else { return false; } } }

  return stk.empty(); }

int main() {
  std::vector<std::string> ptests = {
      "", "()", "()()", "(())", "a(a)a" };
  std::vector<std::string> ftests = {
      "(", ")", ")(", ")()(", "))((" };

  for (const auto& t : ptests) {
    if (!parse(t)) { std::cout << "fail: " << t << std::endl; } }

  for (const auto& t : ftests) {
    if (parse(t)) { std::cout << "fail: " << t << std::endl; } }
}

Answer 2

One important thing you should keep in mind about C++ : Multiple else ifs do not live at the same level. That's because else if is not a single entity, it's an else that belongs to the preceding statement and an ifthat begins a new statement, so

if (cond1)
 a();
else if (cond 2)
 b();
else if (cond 3)
 c();
else
 d();

is actually

if (cond1)
 a();
else { 
  if (cond 2)
   b();
  else {
    if (cond 3)
     c();
    else
     d();
  }
}

Therefore, your check whether the stack is empty needs to be before the check whether the current close parens matches the top of the stack. Otherwise, your program will try to examine the top of the stack when it's empty, and that results in a crash.

---

Also, setting valid = false is not the right thing to do when you find a condition that indicates a non-match. The loop will still continue and can reset valid to true in a later iteration. You need to immediately return false, as you can already see in your pseudocode.