Balanced Parentheses
https://pastebin.com/s0J5af8B
дава 88 от 100 в джъдж, някой може ли да ми каже къде точно ми е грешката.
Тази задача има много варианти, но ако говорим за най-простият (без приоритет между видовете скоби), сте усложнили ненужно решението.
Най-простият (и това автоматично го прави най-добър) алгоритъм за решаването на този проблем) е с използването на един стек.
Четем скобите една по една:
- ако е отваряща, т.е. ( { [, я добавяме в стека
- ако е затваряща, т.е. ) } ], проверяваме в стека:
---- ако е празен => невалиден израз
---- ако скобата е от друг тип => невалиден израз
---- ако скобата е отваряща от правилния тип, продължаваме (след като сме я извадили от стека)
- като свършат всички входни данни, проверяваме дали стека е празен:
---- ако не е празен => невалиден израз
---- празен стек - всички скоби са формирали валидни двойки, т.е. изразът е валиден
едно решение на Мартин Паунов :
Това решение е непълно, защото не покрива случая, когато изразът завършва с една отваряща скоба, напр. ( или (){ и т.н., и ще върне "YES", вместо "NO".
Ако решението минава в Judge, явно тестовете там са непълни, но това е добър пример защо не трябва да разчитаме на това някой друг да ни тества кода, а сами трябва да се грижим за качеството му.
Ето моето решение, мина успешно. Сигурно може да се съкрати малко или да има по умно от това, но не ми се занимава. Задачата с Роботите ми отне време, мисля, че е за звездичка, ако ми се падне на изпит.....от нея точки няма да взема хахаха.
https://pastebin.com/8AbjbTB2
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");
}
}
}
}