2

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;
}
4

2 回答 2

3

关于 C++，您应该记住一件重要的事情：多个else ifs不在同一级别。那是因为else if不是一个单一的实体，它是else属于前面的语句并且if是开始新语句的 an，所以

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

实际上是

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

因此，您检查堆栈是否为空需要在检查当前关闭括号是否与堆栈顶部匹配之前。否则，您的程序将在堆栈为空时尝试检查堆栈顶部，这会导致崩溃。

此外，valid = false当您发现指示不匹配的条件时，设置不是正确的做法。循环仍将继续，并且可以valid在true以后的迭代中重置。您需要立即return false，正如您已经在伪代码中看到的那样。

于 2013-09-28T00:16:17.930 回答
3

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; } }
}
于 2013-09-28T02:51:47.650 回答