• V izrazu bi radi preverili, če so oklepaji / (, ) / postavljeni pravilno

  • (a + b)(c + (d – a))
  • (a + b))w)(c + (d – a))
  • (a + b)(w c + d – a))

• Ideja

  • +1 ko naletimo na predklepaj
  • - 1 ko naletimo na zaklepaj

• Kdaj bo ok?

  • Na koncu 0
  • Ves čas + ali 0

• Kaj pa, če je več parov različnih oklepajev:

  • (, ), [, ], <,>, {,}
• Dva števca?

• Pozor na pravilno gnezdenje!

  • (a + b)[c + (d – a])
  • ([a + b])[c + [d – (a + d)]]
• Pomembni so le oklepaji, ostali znaki nas ne zanimajo

• Dokler oklepaj ne dobi zaklepaja, ga moramo hraniti

• Vedno mora zaklepaj dobiti “najbolj sveži” predklepaj

  • Last In First Out
• Predklepaje hranimo v skladu

• Ko naletimo na zaklepaj, mora biti na vrhu sklada ustrezen predklepaj

  • Če ga ni, ... napaka!
• Na koncu mora biti sklad prazen

• Pripravi sklad

• Za vse znake v izrazu

  • Če je znak predklepaj, ga vstavi v sklad

  • Če je znak zaklepaj

    • Če je sklad prazen:

      • NAPAKA
    • Poglej vrh sklada.

    • Če je na vrhu napačen predklepaj:

      • NAPAKA
    • Odstrani vrhnji elt iz sklada (je že dobil svoj zaklepaj)

• Če je sklad prazen

  • Oklepaji so postavljeni pravilno

algoritem SoPravilno(izraz){
  # ali so v nizu izraz oklepaji postavljeni pravilno
  hrani = new Sklad()
  for znak in izraz # pregledamo vse znake
    if znak je predklepaj :
       hrani.Vstavi(znak) # predklepaj bo počakal na svoj zaklepaj
    else :
       if znak je zaklepaj :
         if hrani.Prazen() :
            return false # nihče ne čaka na ubogi zaklepaj
          if hrani.Vrh() ne ustreza zaklepaju, ki je v znak :
            return false # napačno gnezdenje!
         # zaklepaj je dobil ustrezni par na skladu
         hrani.Odstrani()
       # ostali znaki nas ne zanimajo
  # ce ni cakajocih zaklepajev je OK, drugace pa ne
  return hrani.Prazen()

public static bool soPravilno(string izraz){
  // ali so v izrazu oklepaji postavljeni pravilno
  Sklad<char> hrani = new Sklad<char>();
  for (int i = 0; i < izraz.Length; i++) {
    znak = izraz[i];
    if znak je predklepaj
       hrani.Vstavi(znak); // predklepaj bo počakal na svoj zaklepaj
    else {
       if znak je zaklepaj
         if hrani.Prazen() return false; // nihče ne čaka na ubogi zaklepaj
          if hrani.Vrh() ni ustreza zaklepaju, ki je v znak
            return false; // napačno gnezdenje!
         // zaklepaj je dobil ustrezni par na skladu
         hrani.Odstrani();
       // ostali znaki nas ne zanimajo
    }
  }
  // ce ni cakajocih zaklepajev je OK, drugace pa ne
  return hrani.Prazen();
}

• Oglejmo si, kaj se dogaja s skladom, če podamo izraz

  • (-2)+[[6+8]*(3 – [5*2])]
  • ([(()]))
  • (([][][])
  • (a + b)[c + (d – a])
  • ([a + b])[c + [d – (a + d)]]
  • ...

• Naj bo matrika A dimenzije k j

• Zmnožimo jo lahko z matriko B dimenzije

  • j n

• Za to potrebujemo

  • k * j * n množenj števil

• Matriko velikosti a b lahko zmnožimo samo z matriko velikosti b c

  • Za to potrebujemo a * b * c množenj

• Primer:

  • A : 10 5
  • B : 5 10
  • C : 10 5
  • D : 5 10

  • Kako izračunati A B C D (rezultat bo enak, a načini, kako priti do njega so (vsaj) trije!)

    • (A B) (C D)

      • 500 (za AB) + 500 (za CD) + 1000 (AB je 10 10, CD ke 10 10) = 2000 op

    • A ((B C) D)

      • 250 (BC) + 250 (množimo dobljeni produkt BC z D) + 500 (vse skupaj še z A) = 1000 op

    • (A (B C)) D

      • 250 (BC) + 250 (z A) + 500 (še z D) = 1000 op

• Za izračun optimalnega načina množenja

  • Kdaj drugič
  • Dinamično programiranje