Условие
Дана конечная последовательность, состоящая из левых и правых скобок различных заданных типов. Как определить, можно ли добавить в нее цифры и знаки арифметических действий так, чтобы получилось правильное арифметическое выражение.
Входные данные
$latex ({([])})$
Выходные данные
Yes.
Код
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 |
import java.util.*; import java.lang.*; import java.io.*; class Ideone { public static class stack { char arr[] = new char[10]; int current; stack(){current = 0;}; void push(char x) { arr[current] = x; current++; } void pop() { current--; } char back() { return arr[current-1]; } int size() { return current; } }; public static void main (String[] args) throws java.lang.Exception { String brace; Scanner input = new Scanner(System.in); brace = input.nextLine(); stack x = new stack(); char a = brace.charAt(0); if(a == '(' || a == '{' || a== '[') { for(int i=0;i<brace.length();i++) { a = brace.charAt(i); if(a == '(' || a == '{' || a== '[') x.push(a); else if(Math.abs(a - x.back()) < 3 && x.size() != 0) { x.pop(); } else { System.out.println("No"); System.exit(0); } } if(x.size() == 0) { System.out.println("Yes"); } else System.out.println("No"); } else { System.out.println("No"); System.exit(0); } } } |
Решение
Арифметическое выражение является правильным если каждой открывающей скобке соответствует единственная закрывающая. Что бы убедится в правильности выражения необходимо создать класс $latex stack$, в который поочередно записываются открывающиеся скобки. Если встречается закрывающая скобка того же типа, что и последняя открывающая, то они обе удаляются, так как не влияют на правильность выражения. Если же закрывающая скобка не соответствует типу последней открывающей, то такое арифметическое выражение не является правильным. Если после обработки всей последовательности в стеке не осталось элементов, то такое выражение является правильным. В случае отсутствия скобок выражение также правильное.
Пример работы программы можно увидеть на сайте ideone.
Условие задачи.