проблема балансовых скобок (всегда хороший результат) - PullRequest
Новая
       23

проблема балансовых скобок (всегда хороший результат)

0 голосов
/ 29 марта 2020

Мне нужно написать программу, которая уравновешивает строку в скобках. Я написал программу, но не имеет значения, какую строку я ввожу, потому что программа всегда говорит, что строка хорошая. Вот код:

файл заголовка 

#ifndef HEADER_H_
#define HEADER_H_
#include <string>

struct Element {
    char data;
    Element* link;
};

typedef Element* Stack;

void initStack(Stack& S);
void push(Stack& S, int a);
void pop(Stack &S);
int top(Stack& S);
bool isEmpty(Stack &S);
bool goodPair(char deschis, char inchis);
bool check(std::string s);

#endif

файл функций 

#include <iostream>
#include <string>
#include "header.h"
using namespace std;

void initStack(Stack& S)
{
    S = nullptr;
}

void push(Stack& S, int a)
{
    Element*nou = new Element;
    nou->data = a;
    nou->link = S;
    S = nou;
}

void pop(Stack& S)
{
    Stack aux = S;
    S = S->link;
    delete(aux);
}

int top(Stack& S)
{
    if (isEmpty(S))
        return int();
    return S->data;
}

bool isEmpty(Stack &S)
{
    if (S == 0)
        return true;
    else
        return false;
}

bool goodPair(char deschis, char inchis)
{
    if (deschis == '(' && inchis == ')')
        return true;
    else if (deschis == '[' && inchis == ']')
        return true;
    else if (deschis == '{' && inchis == '}')
        return true;
    else if (deschis == '<' && inchis == '>')
        return true;
    else
        return false;
}

bool check(std::string s)
{
    Element* S;
    for (int i = 0; i < s.length(); i++)
    {
        if (s[i] == '(' || s[i] == '[' || s[i] == '{' || s[i] == '<')
            push(S, s[i]);
        else
        {
            if (s[i] == ')' || s[i] == ']' || s[i] == '}' || s[i] == '>')
                if (isEmpty(S) || !goodPair(top(S), s[i]))
                    return false;
                else
                    pop(S);
        }
    }
    if (isEmpty(S))
        return false;
    else
        return true;

}

основной файл 

#include <iostream>
#include <string>
#include "header.h"
using namespace std;

int main()
{
    Stack S;
    initStack(S);
    string s;
    cout << "Write the string:";
    cin >> s;
    if (check(s))
        cout << "Good";
    else
        cout << "Bad";
    return 0;

}

Я использовал стек и прошел каждый символ. Если символ является открывающей скобкой, я помещаю его в стек. Когда символ является закрывающей скобкой, я сравниваю его с вершиной стека. Если хорошо, я открываю верхнюю часть стека.

1 Ответ

0 голосов
/ 29 марта 2020

Вы создаете указатель на Element (с псевдонимом Stack) S в main() и инициализируете его с nullptr, используя initStack(), и затем вы больше не используете эту переменную. Вместо этого вы создаете локальную S в функции check() и используете ее неинициализированной, что приводит к UB.

Похоже, вы запутались, называя их при вызове S (переменная в main() переменная в check(), все ссылочные параметры все называются S). Это не противозаконно, но похоже, что вы запутались. (вы даже вызвали std::string строчные буквы s, чтобы увеличить путаницу)

Также у вас есть логическая ошибка в вашей функции: 

if (isEmpty(S))
    return false;
else
    return true;

должно быть наоборот, если стек пуст, то строка сбалансированный, а не наоборот. Поэтому замените его на: 

return isEmpty( S );
...