Анализ партирования с использованием класса шаблонов стека в C++

Question

У меня есть домашнее задание и его просто прослушивание в течение последних двух дней, я делаю именно то, что псевдокод и до сих пор еще не получил его. Например, если я ввел «mike» или «mike» 123 », моя программа выйдет из строя из-за того, что стек пуст ... Из того, что я наблюдаю, программа выйдет из строя, когда: - Стек пуста - И есть закрывающая скобка PS: с помощью us2012 я могу исправить проблему сбоя. Однако результат неверен. Вместо распечатки «недействителен», он выдает «действительный»

:(

Вот псевдокод из моего профессора:

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 

и вот то, что я до сих пор:

.cpp файл

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: г ++ -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

Одна важная вещь, которую вы должны иметь в виду о C++: Несколько else if s сделать не живут на том же уровне. Это потому, что else if не является единым целым, что это else, что принадлежит к предыдущему заявлению и if, что начинается новое заявление, так

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(); 
    } 
} 

Поэтому чек ли стек пуст должен быть до проверить, соответствует ли текущий близкий parens верхней части стека. В противном случае ваша программа попытается проверить верхнюю часть стека, когда она пуста, и это приведет к сбою.

---

Кроме того, установка valid = false не то, что нужно делать, когда вы найдете условие, которое указывает на неигровые. Цикл будет продолжаться и может быть сброшен valid на true на более поздней итерации. Вам нужно сразу же return false, как вы уже можете видеть в своем псевдокоде.