Професионална програма
Loading...
+ Нов въпрос
MartinBG avatar MartinBG 3751 Точки

Тази задача има много варианти, но ако говорим за най-простият (без приоритет между видовете скоби), сте усложнили ненужно решението.

Най-простият (и това автоматично го прави най-добър) алгоритъм за решаването на този проблем) е с използването на един стек.

Четем скобите една по една:

- ако е отваряща, т.е. ( { [, я добавяме в стека

- ако е затваряща, т.е. ) } ], проверяваме в стека:

    ---- ако е празен => невалиден израз

    ---- ако скобата е от друг тип => невалиден израз

    ---- ако скобата е отваряща от правилния тип, продължаваме (след като сме я извадили от стека)

- като свършат всички входни данни, проверяваме дали стека е празен:

    ---- ако не е празен => невалиден израз

    ---- празен стек - всички скоби са формирали валидни двойки, т.е. изразът е валиден

0
26/05/2020 17:41:03
MartinBG avatar MartinBG 3751 Точки

@Sirakov4444

Това решение е непълно, защото не покрива случая, когато изразът завършва с една отваряща скоба, напр. ( или (){ и т.н., и ще върне "YES", вместо "NO".

Ако решението минава в Judge, явно тестовете там са непълни, но това е добър пример защо не трябва да разчитаме на това някой друг да ни тества кода, а сами трябва да се грижим за качеството му.

0
27/05/2020 17:35:51
chaneto avatar chaneto -1 Точки

Ето моето решение, мина успешно. Сигурно може да се съкрати малко или да има по умно от това, но не ми се занимава. Задачата с Роботите ми отне време, мисля, че е за звездичка, ако ми се падне на изпит.....от нея точки няма да взема хахаха.

https://pastebin.com/8AbjbTB2

0
mitkomik avatar mitkomik 12 Точки
package BalancedBrackets;

import java.util.ArrayDeque;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String input = scanner.nextLine();
        ArrayDeque<Character> openDecue = new ArrayDeque<>();

        if (input.length() % 2 != 0) {
            System.out.println("NO");

        } else {

            for (int i = 0; i < input.length(); i++) {
                char temp = input.charAt(i);
                if (temp == '(' || temp == '[' || temp == '{') {
                    openDecue.push(temp);
                } else {
                    switch (temp) {
                        case ')':
                            if (openDecue.peek().equals('('))
                                openDecue.pop();
                            break;
                        case ']':
                            if (openDecue.peek().equals('['))
                                openDecue.pop();
                            break;
                        case '}':
                            if (openDecue.peek().equals('{'))
                                openDecue.pop();
                            break;
                    }
                }
            }
            if (openDecue.isEmpty()) {
                System.out.println("YES");
            } else {
                System.out.println("NO");
            }
        }
    }
}
0