Oppgave 1 og 2

Her ligger hele klassen TabellStakk<T>, inklusive metodene nullstill og toString:

import java.util.Arrays;
import java.util.Collection;
import java.util.NoSuchElementException;
import java.util.StringJoiner;

public class TabellStakk<T> implements Stakk<T>
{
  private T[] a;                    // en generisk tabell
  private int antall;               // antall verdier på stakken

  @SuppressWarnings("unchecked")    // konvertering: Object[] -> T[]
  public TabellStakk(int lengde)    // valgfri tabellengde
  {
    a = (T[]) new Object[lengde];   // oppretter tabellen
    antall = 0;                     // stakken er tom
  }

  public TabellStakk()
  {
    this(8);                        // lengde lik 8
  }

  @Override
  public int antall()
  {
    return antall;
  }

  @Override
  public boolean tom()
  {
    return antall == 0;
  }

  @Override
  public void leggInn(T verdi)
  {
    if (antall == a.length)
      a = Arrays.copyOf(a,antall == 0 ? 1 : 2*antall);  // dobler

    a[antall++] = verdi;
  }

  @Override
  public T kikk()
  {
    if (antall == 0) throw
      new NoSuchElementException("Stakken er tom!");

    return a[antall-1];
  }

  @Override
  public T taUt()
  {
    if (antall == 0) throw
      new NoSuchElementException("Stakken er tom!");

    antall--;

    T temp = a[antall];
    a[antall] = null;
    return temp;
  }

  @Override
  public void nullstill()
  {
    for (int i = 0; i < antall; i++) a[i] = null;
    antall = 0;
  }

  @Override
  public String toString()   // bruker StringJoiner
  {
    StringJoiner s = new StringJoiner(", ", "[", "]");
    for (int i = antall - 1; i >= 0; i--)
      s.add(a[i] == null ? "null" : a[i].toString());
    return s.toString();
  }

  public String toString2()  // bruker StringBuilder
  {
    if (tom()) return "[]";

    StringBuilder s = new StringBuilder();
    s.append('[');
    s.append(a[antall-1]);

    for (int i = antall - 2; i >= 0; i--)
      s.append(',').append(' ').append(a[i]);

    s.append(']');
    return s.toString();
  }

} // class TabellStakk

Oppgave 3

  public static <T> void snu(Stakk<T> A)
  {
    Stakk<T> B = new TabellStakk<T>();
    Stakk<T> C = new TabellStakk<T>();

    while (!A.tom()) B.leggInn(A.taUt());
    while (!B.tom()) C.leggInn(B.taUt());
    while (!C.tom()) A.leggInn(C.taUt());
  } 

Oppgave 4

  public static  void kopier(Stakk<T> A, Stakk<T> B)
  {
    Stakk<T> C = new TabellStakk<T>();
    while (!A.tom()) C.leggInn(A.taUt());
    while (!C.tom())
    {
      T t = C.taUt();
      B.leggInn(t);
      A.leggInn(t);
    }
  }

Oppgave 5

Noen vil kanskje tenke på en løsning som dette. Forklar hvorfor dette ikke virker. Dvs. hvorfor dette ikke snur stakken A:

  public static <T> void snu(Stakk<T> A)
  {
    // Dette vil ikke snu stakken A
    Stakk<T> B = new TabellStakk<T>();
    while (!A.tom()) B.leggInn(A.taUt());
    A = B;
  }

Metoden som kommer her vil imidlertid snu stakken:

  public static <T> void snu(Stakk<T> A)
  {
    Stakk<T> B = new TabellStakk<T>();
    int n = A.antall() - 1;

    while (n > 0)
    {
      T temp = A.taUt();
      for (int j = 0; j < n; j++) B.leggInn(A.taUt());
      A.leggInn(temp);
      while (!B.tom()) A.leggInn(B.taUt());
      n--;
    }
  } 

Oppgave 6

  public static <T> void kopier(Stakk<T> A, Stakk<T> B)
  {
    int n = A.antall();

    while (n > 0)
    {
      for (int j = 0; j < n; j++) B.leggInn(A.taUt());
      T temp = B.kikk();
      for (int j = 0; j < n; j++) A.leggInn(B.taUt());
      B.leggInn(temp);
      n--;
    }
  }

Oppgave 7

  // sorterer slik at den minste kommer øverst på stakken

  public static <T> void sorter(Stakk<T> A, Comparator<T> c)
  {
    Stakk<T> B = new TabellStakk<T>();
    T temp; int n = 0;

    while (!A.tom())
    {
      temp = A.taUt();
      n = 0;
      while (!B.tom() && c.compare(temp,B.kikk()) < 0)
      {
        n++; A.leggInn(B.taUt());
      }
      B.leggInn(temp);
      for (int i = 0; i < n; i++) B.leggInn(A.taUt());
    }

    while (!B.tom()) A.leggInn(B.taUt());
  } 

Oppgave 8

Opprett en stakk. Gå så gjennom tegnstrengen. En venstre-parentes legges på stakken. Finner vi en høyre-parentes tar vi en venstre-parentes fra stakken. Disse hører sammen. En tom stakk betyr at vi har en høyre-parentes som ikke har noen tilhørende venstre-parentes. Hvis det er noe igjen på stakken når vi er ferdig med tegnstrengen, betyr det at vi har en venstre-parentes (eller parenteser) uten tilhørende høyre-parentes.

Vi lager en metode der parentestypen går inn som parameter:

  public static void sjekkParenteser(String tekst, char v, char h)
  {
    Stakk<Character> stakk = new TabellStakk<Character>();

    for (int i = 0; i < tekst.length(); i++)
    {
      if (tekst.charAt(i) == v) stakk.leggInn(v); // venstre-parentes
      else if (tekst.charAt(i) == h)  // høyre-parentes
      {
        if (stakk.tom())
        {
          System.out.println("Det mangler en venstre-parentes");
          return;
        }
        stakk.taUt();
      }
    }

    if (!stakk.tom())
      System.out.println("Det mangler en høyre-parentes");
  }

Oppgave 9

  String s = "int n = (1 + 2) * (3) - 4) + (5 / 6);";
  sjekkParenteser(s,'(',')');