Izpitno vprašanje RAČ2PRA 6200

Iz MaFiRaWiki

GFDL Avtor tega članka je študent/ka JožicaPavlovič.

Pripravil/a ga je pri predmetu Računalništvo 2 (FMF PRA).


Kljub temu ste vsi vabljeni k urejanju in popravkom, saj je bistvo wikija ravno v sodelovalnem delu.


Vprašanje

Preveri, če so v danem izrazu oklepaji postavljeni pravilno. V izrazu lahko nastopajo ( in [ oklepaji. Vsak predklepaj mora imeti zaklepaj, prav tako pa morajo biti oklepaji pravilno gnezdeni. Izraz je dan kot niz, na voljo pa je sklad, v katerem lahko hranimo znake. Tako v [a(b(]b]bb fbf] oklepaji niso, v [a(b()b)b[b f]bf] pa so postavljeni pravilno.


Odgovor

Nalogo lahko rešimo z metodo public static boolean oklepaji(String niz), ki vrne true, če so v nizu oklepaji postavljeni pravilno, in false sicer. V zrazu imamo dve vrsti oklepajev - [/] in (/).


Pri tem algoritmom si pomagamo s skladom, v katerem bodo vsebovani znaki. Najprej preverimo, če je i-ti znak v nizu predklepaj, ga damo v sklad. Če pa je znak zaklepaj in prvi element v skladu predklepaj, element iz sklada odstranimo, sicer vrnemo false.

  1.  
  2. public class Oklepaji{
  3. public static boolean oklepaji(String niz){
  4. Sklad<Character> s = new Sklad<Character>();
  5. for(int i = 0; i<niz.length(); i++){
  6. char znak = niz.charAt(i); //znak je i-ti znak niza
  7. if((znak == '(')||(znak == '[')){
  8. s.vstavi(znak);
  9. }
  10. else if(znak == ']'){
  11. if(s.vrh() == '['){
  12. s.odstrani();
  13. }
  14. else{return false;}
  15. }
  16. else if(znak == ')'){
  17. if(s.vrh() == '('){
  18. s.odstrani();
  19. }
  20. else{return false;}
  21. }
  22. }
  23. return s.prazen();
  24. }
  25.  
  26. //preiskus metode oklepaji
  27. public static void main(String[] args) {
  28. System.out.println(oklepaji("[a(b()b)b[b f]bf]"); //true
  29. System.out.println(oklepaji("[a(b(]b]bb fbf]"); //false
  30. }
  31. }
Osebna orodja