Wyrażeniem nawiasowym nazywamy dowolny skończony ciąg nawiasów: „[” i „]”. Przykładowo: [ [ ] [ ] ]
Wyrażenie nawiasowe jest poprawne, jeśli:
– jest wyrażeniem pustym (nie zawiera żadnych nawiasów)
– jest postaci AB, gdzie A i B są poprawnymi wyrażeniami nawiasowymi
– jest postaci [ A ], gdzie A jest poprawnym wyrażeniem nawiasowym
Przykład: wyrażenia [ [ ] ] oraz [ [ ] [ ] ] są poprawne. Niepoprawne jest za to wyrażenie [ ] ] [ ] ].
Niech w1, w2, …, wn będą kolejnymi nawiasami w pewnym wyrażeniu nawiasowym W. Przyjmijmy teraz, że z każdym nawiasem otwierającym „[” wiążemy liczbę +1, a z każdym nawiasem zamykającym „]” – liczbę -1. Niech si będzie liczbą związaną z nawiasem wi. Wówczas głębokością nawiasu wk w wyrażeniu W nazywamy sumę:
Sk = s1 + s2 + … + sk
Głębokością wyrażenia W nazwiemy największą głębokość jego nawiasów, czyli maksimum z liczb Sk.
Zadanie 1.
|
Wskaż, czy dane wyrażenie nawiasowe jest poprawne. Wpisz Tak, jeśli wyrażenie jest poprawne lub Nie – jeśli nie jest poprawne. Wyrażenie nawiasowe |
Poprawne (Tak/Nie) |
|
|
[ ] |
Tak |
|
|
[ ] [ ] |
||
|
[ [ ] [ ] ] [ ] ] |
||
|
[ ] [ [ ] [ [ ] [ [ ] [ ] ] ] ] |
||
|
[ [ ] [ ] [ [ [ ] [ ] ] [ ] ] ] |
||
Zadanie 2.
|
Dla zadanych przykładów policz głębokość wyrażenia. Wyrażenie nawiasowe |
Głębokość |
|
[ ] |
1 |
|
[ ] [ ] |
|
|
[ [ ] [ ] ] |
|
|
[ [ ] [ [ ] ] ] |
|
|
[ [ [ [ ] [ ] ] [ ] ] ] |
Zadanie 3.
Dane w pliku dane2_3.txt zapisano w oddzielnych wierszach. W każdym wierszu znajduje się poprawne wyrażenie nawiasowe złożone z nawiasów kwadratowych (nieoddzielonych żadnym znakiem).
Napisz program, który dla zadanych wyrażeń nawiasowych w pliku dane2_3.txt obliczy ich głębokości.
Rozwiązanie
Dla danych z pierwszych czterech wierszy w pliku dane2_3.txt:
[][][]
[[[]]]
[[][][]]
[[[]]]
Odpowiedź
1
3
2
3
Utwórz plik o nazwie dane2_3.txt i skopiuj do niego poniższe dane.
[][][]
[[[]]]
[[][][]]
[[[]]]
[][][][]
[[[[]]]]
[[[][]][]]
[[[[]]]]
[][][[]]
[[[]]]
[[][[]][]]
[[[[][]]]]
[][][]
[[[]]]
[[][[][[]][]][[][]]]
[[[[][][][[]]]]]
[][][][][][][][]
[[[]]][]
[[][][][[[[]]]]]
[[[]]]
[[][][]][[][][]][[][][]]
[[[[]]][[[]]][[[]]]]
[[[[][][]][[][][]]]]
[[[[[[]]]]]]
[][[[[]]]][]
[[[[[][][]]]]]
[[][][]][][[[]]]
[[[[[]]][[[]]][[[]]]]]
[][][][][][][][][][[[[[[]]]]]]
[[[[]]][[[[][]]]]]
[[[[[][][]][[][][]][[][][]][[][][]][[][][]]]]]
[[[[]]][[[]]][[]][[[[]]]][]]
[][][][[]][[]][[]][[]]
[[][][[[]]]]
[[[[[[][][]][[][][]]]]]]
[[[[[[[[[]]]]]]]]]
[][][][][][][][[]][][][][[]][][[[]]]
[[[[[]]][[[]]][[[]]][[[]]][[[]]][]]]
[[[][][]][][[][][]]]
[[][[]][][[]][[[]]]]
[][][][][][][][][][[[[]]]][[[[]]]][[[][][]]]
[[[][[]][][[]][[[]]]][[][[]][][[]][[[]]]]]
[[][][][][][][][[]][][][][[]][][[[]]]][][][][][][][][[]][][][][[]][][[[]]]
[[[][[[[[[]]]]]]]]
[[[][][][[[]]][[][][]][[][][]]]]
[[[][][][[[]]]]]
[[][][]][[][][][]][[][][][][]][[][][][[]][][]]
[[[[[[]]][[[]]][[[]]][[[]]][[[]]][[[]]]]]]
[][][[[[][]][]][[][[][][]][]]]
[[[[[[[[[[[[[[[[[]]]]]]]]]]]]]]]]]
Zadanie 4.
Napisz program, który dla wyrażeń nawiasowych zapisanych w pliku dane2_4.txt sprawdzi, czy są one poprawne. Dane w pliku zapisano po jednym wyrażeniu w wierszu, podobnie jak w pliku o nazwie dane2_3.txt.
Rozwiązanie
Dla danych z pierwszych czterech wierszy pliku dane2_4.txt:
[][][]
[[[]]]
[[][][]]
[[[]]]]
Odpowiedź
tak
tak
tak
nie
Utwórz plik o nazwie dane2_4.txt i skopiuj do niego poniższe dane.
[][][]
[[[]]]
[[][][]]
[[[]]]]
[][][][]
[[[[]]]]
[[[][]][]]
[[[[]]]]
[][][[]]
[[[[]]]
[[][[]][]]
[[[[][]]]]
[][][]
[[[]]]
[[][[[][[]][[]][[][]]]
[[[[][][][[]]]]]
[][][][][][][][]
[[[]]][]
[[][][][[[[]]]]]
[[[]]]]]]
[[][][]][[][][]][[][][]]
[[[[]]][[[]]][[[]]]]
[[[[][][]][[][][]]]]
[[[[[[]]]]]]
[][[[[]]]][]
[[[[[][][]]]]]
[[][][]][][[[]]]
[[[[[]]][[[]]][[[]]]]]
[][][][][][][][][][[[[[[]]]]]]
[[[[]]][[[[][]]]]]
[[[[[][][]][[][][]][[][][]][[][][]][[][][]]]]]
[[[[]]][[[]]][[]][[[[]]]][]]
[][][][[]][[]][[]][[]]
[[][][[[]]]]
[[[[[[][][]][[][][]]]]]]]
[[[[[[[[[]]]]]]]]]
[][][][][][][][[]][][][][[]][][[[]]]
[[[[[]]][[[]]][[[]]][[[]]][[[]]][]]]
[[[][][]][][[][][]]]
[[][[[]][][[[]][[[]]]]
[][][][][][][][][][[[[]]]][[[[]]]][[[][][]]]
[[[][[]][][[]][[[]]]][[][[]][][[]][[[]]]]]
[[][][][[][][][][[]][][][][[]][][[[]]]][][][][][[][][][[[]][][][][[[]][][[[]]]
[[[][[[[[[]]]]]]]]
[[[][][][[[]]][[][][]][[][][]]]]
[[[][][][[[]]]]]
[[][][]][[][][][]][[][][][][]][[][][][[]][][]]
[[[[[[]]][[[]]][[[]]][[[]]][[[]]][[[]]]]]]
[][][[[[][]][]][[][[][][]][]]]
[[[[[[[[[[[[[[[[[]]]]]]]]]]]]]]]]]]]]]]]]]]]