Относно Problem 4 Brackets

sun_seeker 15 Точки

Относно Problem 4 Brackets

Въпросът ми е по-скоро към Жоро.

Ще може ли в началото на лекцията да споделиш някакво по-красиво решение на тази задача? Аз лично се справих с vector и няколко if-a, но си мисля, че би трябвало да има някаква хитринка.

Благодаря!

Тагове:

12/12/2017 16:35:41 C++ Fundamentals

MartinBG 4803 Точки

Best Answer

Нямам условието на задачата, но съдейки по името ѝ, предполагам става дума за валидиране на скобите в (псевдо)математически израз?

Класическото решение на този тип проблеми е със стек.

Алгоритъмът най-общо е следният: обработваш входните данни последователно, като вкарваш всяка отваряща скоба в стека, а при срещане на затваряща - вадиш последната скоба от стека и правиш валидация (тип или каквото специфично има в условието); ако стека е празен или скобата не е от верния тип, значи изразът е невалиден. За да е валиден израза, накрая стека трябва да бъде празен.

12/12/2017 23:07:09 12/12/2017 23:21:39

sun_seeker 15 Точки

Еми на, кой да се сети.... аз по тъпия начин. Мерси все пак, ще го пробвам и така.

12/12/2017 23:11:32

fantom4e 24 Точки

Аз, лично скалъпих нещо доста импровизирано с лека мисъл за използване на рекурсия.
https://github.com/fantom4e/Homework

15/12/2017 00:36:51

sun_seeker 15 Точки

Мдаа, доста дългичък вариант :) и моето е нещо подобно.

15/12/2017 14:56:48

ItsGosho 5 Точки

Ето какво написах набързо, не са използвани стекове и т.н

Базира се на това, че ако имаме след дадена скоба невалидна такава, то директно целият израз е грешен заради йерархията им.

#include <iostream>
#include <string>

using namespace std;

int main() {
    string consoleLine;
    getline(cin, consoleLine);

    bool invalid = false;

    int i = 0;
    while (true) {
        i++;

        if (i == consoleLine.size() || invalid)
            break;

        char bracket = consoleLine[i];
        char nextBracket = consoleLine[i + 1];

        if (bracket == '(')
            switch (nextBracket) {

                case ')':
                    consoleLine.erase(consoleLine.begin() + i, consoleLine.begin() + i + 2);
                    i = 0;
                    break;
                case '}':
                case ']':
                case '{':
                case '[':
                    invalid = true;
                    break;
            }
        else if (bracket == '{')
            switch (nextBracket) {

                case '}':
                    consoleLine.erase(consoleLine.begin() + i, consoleLine.begin() + i + 2);
                    i = 0;
                    break;

                case ')':
                case ']':
                    invalid = true;
                    break;
            }
        else if (bracket == '[')
            switch (nextBracket) {

                case ']':
                    consoleLine.erase(consoleLine.begin() + i, consoleLine.begin() + i + 2);
                    i = 0;
                    break;

                case ')':
                case '}':
                case '{':
                    invalid = true;
                    break;
            }
    }

    cout << (invalid ? "invalid" : "valid");
}

17/02/2021 19:10:51