1

Тема: C++ Перевірка дужок. Стек

Привіт. В задачі потрібно перевірити чи співпадають відкриваючі та закриваючі дужки. Реалізацію задумав наступну: 1. вводимо строку; 2. проходимось циклом по кожному елементу строки 3. якщо знаходимо відкриваючу дужку - кладемо її в стек на початок 4. якщо дужка закриваюча - звіряємо її з тією, що у верхівці стеку; 5. якщо співпало - продовжуємо, ні - виходимо з циклу
Біда в тому, що у мене програма не кладе дужки в стек
В чому проблема?

#include<iostream>
#include <string>

using namespace std;

class Bracket
{
    struct Node
    {
        char bracket;
        Node *pNext;
    };
    int count;
    Node *pHead;
    Node *pTail;

public:
    Bracket()
    {
        pHead = pTail = nullptr;
        count = 0;
    }

    Bracket(char obj)
    {
        Node *pCur = new Node;
        pCur->bracket = obj;
    }

    bool addBracket(char obj)
    {

        Node *pNew = new Node;
        if (pNew)
        {
            if (count == 0)
            {
                pHead = pTail = nullptr;
            }
            pNew->bracket = obj;
            pNew->pNext = nullptr;
            if (pTail = nullptr)
            {
                pHead = pTail = pNew;
            }
            else if (pHead == pTail)
            {
                pHead->pNext = pNew;
                pTail = pNew;
            }
            else
            {
                pTail->pNext = pNew;
                pTail = pNew;
            }
            count++;
            return true;
        }
        return false;
    }

    bool checkBrakets(char example)
    {
        if (count == 0 || pHead->bracket != example)
        {
            return false;
        }
        Node *pDel = new Node;
        pDel = pHead;
        pHead = pHead->pNext;
        delete pDel;
        pDel = nullptr;
        count--;
        return true;
    }
};

void main()
{
    string some_text;
    cout << "Enter your brackets : ";
    getline(cin, some_text);
    Bracket obj;
    for (int i = 0; i < sizeof(some_text); ++i)
    {
        if (some_text[i] == '(' || some_text[i] == '[' || some_text[i] == '{')
        {
            obj.addBracket(some_text[i]);
        }
        if (some_text[i] == ')' || some_text[i] == ']' || some_text[i] == '}')
        {
            if (obj.checkBrakets(some_text[i]))
            {
                continue;;
            }
            else
            {
                cout << "Brackets do not meet each other!" << endl;
                break;
            }
        }
        cout << "Brackets confirmed" << endl;
    }
    system("pause");
}

2

Re: C++ Перевірка дужок. Стек

Коли щось складеться до стеку, ви використовуєте new. Логічним видається, що під час діставання щось має виділятися, правда?

3

Re: C++ Перевірка дужок. Стек

так от же ж:

bool checkBrakets(char example)
    {
        if (count == 0 || pHead->bracket != example)
        {
            return false;
        }
        Node *pDel = new Node;
        pDel = pHead;
        pHead = pHead->pNext;
        delete pDel;
        pDel = nullptr;
        count--;
        return true;
    }

але проблема в тому, що не кладеться

4

Re: C++ Перевірка дужок. Стек

Дивіться уважніше: в addBracket є один new (довжина стеку зростає), в checkBrakets - один new і один delete (довжина стеку не змінюється).

5

Re: C++ Перевірка дужок. Стек

чому ж не змінюється: 1. ноді pDel ми присвоюємо ноду pHead 2. pHead->pNext стає у вершину стеку 3. Видаляємо pDel і зменшуємо count. Оскільки працюємо з вказівниками, то разом з pDel видаляємо і колишню pHead.

Проблема в тому, що при створенні самого першого елементу стеку програма пропускає перевірку
if (pTail = nullptr)
            {
                pHead = pTail = pNew;
            }
і переходить. Блін, олень я. Треба робити перерви, бо сидіння за ПК цілими днями нідо чого хорошого не приводить, а лише до таких тупих помилок
+ деякі перевірки некоректні
важко

6

Re: C++ Перевірка дужок. Стек

Працюючий код:

#include<iostream>
#include <string>

using namespace std;

class Bracket
{
    struct Node
    {
        char bracket;
        Node *pNext;
    };
    int count;
    Node *pHead;

public:
    Bracket()
    {
        pHead = nullptr;
        count = 0;
    }

    Bracket(char obj)
    {
        Node *pCur = new Node;
        pCur->bracket = obj;
    }

    bool addBracket(char obj)
    {

        Node *pNew = new Node;
        if (pNew)
        {
            if (count == 0)
            {
                pHead = nullptr;
            }
            pNew->bracket = obj;
            pNew->pNext = pHead;
            pHead = pNew;
            count++;
            return true;
        }
        return false;
    }

    bool checkBrakets(char example)
    {
        if (count == 0 || pHead->bracket != example)
        {
            return false;
        }
        Node *pDel = new Node;
        pDel = pHead;
        pHead = pHead->pNext;
        delete pDel;
        pDel = nullptr;
        count--;
        return true;
    }
};

void main()
{
    string some_text;
    cout << "Enter your brackets : ";
    getline(cin, some_text);
    Bracket obj;
    for (int i = 0; i < some_text.length(); ++i)
    {
        if (some_text[i] == '(' || some_text[i] == '[' || some_text[i] == '{')
        {
            obj.addBracket(some_text[i]);
        }
        if (some_text[i] == ')' || some_text[i] == ']' || some_text[i] == '}')
        {
            char tmp;
            some_text[i] == ')' ? tmp = '(' : some_text[i] == ']' ? tmp = '[' : tmp = '{';
            if (obj.checkBrakets(tmp))
            {
                cout << "Brackets confirmed" << endl;
            }
            else
            {
                cout << "Brackets do not meet each other!" << endl;
                break;
            }
        }
    }
    system("pause");
}
Подякували: koala1

7

Re: C++ Перевірка дужок. Стек

Рядки 54-55 замініть на

Node *pDel = pHead;

інакше у вас пам'ять тече.
Крім того, в сучасних компіляторах C++ оператор new при помилці кидає виняток, а не повертає 0 (варіант із нулем теж передбачений -

#include <new>
...
x=new(std::nothrow) Node;
Подякували: boshik19831

8

Re: C++ Перевірка дужок. Стек

за пам'ять дякую, а обробку помилок ми ще будемо вчити. Сподіваюсь нам там все детальніше пояснять.