Oppgavesett 4

package Oppgave1;

import java.util.Scanner;
import java.util.Stack;

public class Oppgave1 
{

    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) 
    {
	String expression, again = "";
	Stack<Character> rev = new Stack<Character>();
	
        try
	{
	    Scanner in = new Scanner(System.in);
	    
	    do
	    {
		// Empty the stack
		rev.clear();
		
		expression = in.nextLine();
		
		for (int i = 0; i < expression.length(); i++)
		{
		    // push the word backwards
		    rev.push(expression.charAt(i));
		}
		
		while (rev.size() > 0)
		{
		    // Pop out the characters in reverse
		    System.out.print(rev.pop());
		}
		
		System.out.println();
		System.out.println();
		System.out.print("Reverse another sentence [Y/N]? ");
		System.out.println();
		
		again = in.nextLine();
	    }
	    while (again.equalsIgnoreCase("y"));
	}
	catch (Exception IOException)
	{
	    System.err.println("Input Exception Reported");
	}
    }

}

public void fjern(Stack<Integer> s1)
{
	Stack<Integer> help = new Stack<Integer>();
	while(!s1.empty())
	{
		help.push(s1.pop());
		if(!s1.empty())
			s1.pop();
	}
	while(!help.empty())
	{
		s1.push(help.pop());
	}
}

package Oppgave2;

import java.util.Stack;

/**
 *
 * @author Belazor
 */
public class Oppgave2
{
    public static void fjern(Stack<Integer> s1)
    {
        Stack<Integer> s2 = new Stack<Integer>();
        
        int temp = s1.size();
        for (int i = 0; i < temp; i++)
        {
            if ((s1.peek() % 2) == 1)
	    {
		s2.push(s1.pop());
		continue;
	    }
	    
	    s1.pop();
        }
	
        temp = s2.size();
        for (int i = 0; i < temp; i++)
	{
	    s1.push(s2.pop());
	}
    }

    /**
     * @param args the command line arguments
     */
    public static void main(String[] args)
    {
	Stack<Integer> test = new Stack<Integer>();
        
	for (int i = 7; i > 0; i--)
	{
	    test.push(i);
	}
	
        fjern(test);
        
        System.out.println(test);
    }

}

package Oppgave3;


/**
 *
 * @author Belazor
 */
public class Oppgave3 
{
    boolean sjekk(String tekst)
    {
	// Allocate the boolean variable
	boolean retval = false;
	
	if (!tekst.equals(tekst.toUpperCase()))
	{
	    // Is not upper case
	    return retval;
	}
	
	if (!tekst.matches("[AB]+C[AB]+$"))
	{
	    // Does not match
	    return retval;
	}
	
	// Find out where the C is
	int i = tekst.indexOf('C');
	
	// Find what comes before and after the C
	String prefix = tekst.substring(0, i);
	String postfix = tekst.substring(i + 1);
	
	if (prefix.equals(new StringBuffer(postfix).reverse().toString()))
	{
	    // Check against reversed string 
	    retval = true;
	}
	
	// Return the required value
	return retval;
    }
    /**
     * @param args the command line arguments
     */
    public static void main(String[] args)
    {
        Oppgave3 oppgave = new Oppgave3();
	
	if (oppgave.sjekk("ABABBACABBABA"))
	{
	    System.out.println("String matches.");
	}
	else
	{
	    System.out.println("String does not match.");	    
	}
    }

}

package Oppgave4;

import java.util.Stack;

/**
 *
 * @author Belazor
 */
public class Oppgave4
{

    public static final char PROVD = '0';
    public static final char STI = '+';
    public char[][] grid =
    {
	{' ', ' ', ' ', 'X', ' ', ' ', 'X', 'X', 'X', ' ', ' ', ' ', ' '},
	{' ', 'X', 'X', ' ', ' ', 'X', ' ', ' ', ' ', ' ', 'X', 'X', ' '},
	{' ', ' ', ' ', ' ', ' ', 'X', ' ', 'X', ' ', 'X', ' ', 'X', 'X'},
	{'X', 'X', 'X', 'X', ' ', ' ', ' ', 'X', ' ', 'X', ' ', ' ', ' '},
	{' ', ' ', ' ', 'X', ' ', ' ', ' ', 'X', ' ', 'X', ' ', ' ', ' '},
	{' ', 'X', ' ', 'X', 'X', 'X', 'X', ' ', ' ', ' ', 'X', 'X', ' '},
	{' ', 'X', ' ', ' ', ' ', ' ', ' ', ' ', 'X', ' ', ' ', ' ', ' '},
	{' ', 'X', 'X', 'X', 'X', 'X', 'X', 'X', 'X', 'X', 'X', 'X', 'X'},
	{' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' '}
    };
    private Stack<Posisjon> vei = new Stack<Posisjon>();

    private Stack<Posisjon> pushNyPos(Posisjon npos, Stack<Posisjon> stack)
    {
	if (npos.erGyldig())
	{
	    // merk posisjonen som besøkt
	    grid[npos.rad][npos.kolonne] = PROVD;
	    stack.push(npos);
	}

	return stack;
    }

    private void markerSti(Stack<Posisjon> s)
    {
	while (s.size() > 0)
	{
	    Posisjon pos = s.pop();

	    if (pos.erSti)
	    {
		vei.push(pos);
		grid[pos.rad][pos.kolonne] = STI;
	    }
	}

	System.out.println("Start\t\t[(0,0)]");
	while (vei.size() > 0)
	{
	    Posisjon pos = vei.pop();
	    try
	    {
		// Må peeke for å sammenligne
		Posisjon pos2 = vei.peek();

		if (pos.rad < pos2.rad)
		{
		    // Vi har gått ned
		    System.out.print("S(ned)\t");
		}
		else if (pos.rad > pos2.rad)
		{
		    // Vi har gått opp
		    System.out.print("N(opp)\t");
		}
		else if (pos.kolonne < pos2.kolonne)
		{
		    // Vi har gått til høyre
		    System.out.print("E(høyre)");
		}
		else if (pos.kolonne > pos2.kolonne)
		{
		    // Vi har gått til venstre
		    System.out.print("W(venstre)");
		}
		System.out.println(" \t[" + pos + " -> " + pos2 + "]");
	    }
	    catch (java.util.EmptyStackException e)
	    {
		// And the winrar is us
		System.out.println("Mål! \t\t[" + pos + "]");
	    }
	}
	System.out.println();
    }

    public boolean traverser()
    {
	boolean fremme = false;
	Posisjon pos = new Posisjon(0, 0);

	Stack<Posisjon> stack = new Stack<Posisjon>();

	// Posisjonen til øvre venstre hjørne legges på stakken
	stack = pushNyPos(new Posisjon(0, 0), stack);

	while (!fremme && (!stack.empty()))
	{
	    // Ser på øverste posisjon 
	    pos = stack.peek();

	    pos.erSti = true;
	    
	    //Sjekker om vi er fremme
	    if (pos.rad == grid.length - 1 && pos.kolonne == grid[0].length - 1)
	    {
		// the maze is solved
		fremme = true;
	    }
	    else
	    {
		// Sjekker om det finnes noen veier videre fra øverste posisjon
		// på stakken
		int size = stack.size();
		stack = pushNyPos(new Posisjon(pos.rad, pos.kolonne - 1), stack);
		stack = pushNyPos(new Posisjon(pos.rad, pos.kolonne + 1), stack);
		stack = pushNyPos(new Posisjon(pos.rad - 1, pos.kolonne), stack);
		stack = pushNyPos(new Posisjon(pos.rad + 1, pos.kolonne), stack);

		if (size == stack.size())
		{
		    // Det ikke er noen vei videre, pop stakken.
		    stack.pop();
		}
	    }
	}
	markerSti(stack);
	return fremme;
    }

    @Override
    public String toString()
    {
	String result = "\n";
	for (int rad = 0; rad < grid.length; rad++)
	{
	    for (int kolonne = 0; kolonne < grid[rad].length; kolonne++)
	    {
		result += grid[rad][kolonne] + "";
	    }

	    result += "\n";
	}

	return result;
    }

    private class Posisjon
    {

	private int rad;
	private int kolonne;
	private boolean erSti;

	private Posisjon(int x, int y)
	{
	    rad = x;
	    kolonne = y;
	    erSti = false;
	}

	private boolean erGyldig()
	{
	    boolean svar = false;

	    //Sjekker om vi er innenfor tabellens grenser 
	    if (rad >= 0 && rad < grid.length && kolonne >= 0 && kolonne < grid[rad].length)
	    {
		// Sjekker om cellen er prøvd tidligere eller blokkert. 
		if (grid[rad][kolonne] == ' ')
		{
		    svar = true;
		}
	    }
	    return svar;
	}

	@Override
	public String toString()
	{
	    return "(" + rad + ", " + kolonne + ")";
	}
    }

    public static void main(String[] args)
    {
	Oppgave4 l = new Oppgave4();
	if (l.traverser())
	{
	    System.out.println("Labyrinten er traversert");
	}
	else
	{
	    System.out.println("Labyrinten kan ikke traverseres");
	}
	System.out.println(l);
    }
}

import java.util.*;

public class In2Pos
{
	public static void main(String[] args)
	{
		Stack<Character> stakk = new Stack<Character>();

		String in = args[0];
		int pos = 0;
		while(pos < in.length())
		{
			int presedens = finnPresedens(in.charAt(pos));
			if(presedens == 0)
				System.out.print(in.charAt(pos));
			else 
			{
				while(!stakk.empty() &&  presedens < finnPresedens(stakk.peek()))
				{
					System.out.print(stakk.pop());
				}
				stakk.push(in.charAt(pos));
			}
			pos++;
		}		
		while(!stakk.empty())
		{
			System.out.print(stakk.pop());
		}
	}

	private static int finnPresedens(char ch)
	{
		switch(ch)
		{
			case '+':
			case '-':
				return 1;
			
			case '*':
			case '/':
				return 2;

			default:
				return 0;				
		}
	}
}

package Oppgave5;

import java.util.Stack;

/**
 *
 * @author Belazor
 */
public class Oppgave5 
{
    static String input = "1+2*4/5-7+3/6";
    static String output = "";
    static Stack<Character> stack = new Stack<Character>();    
    
    public static void operator(char in, int precedence_new) 
    {
	while (!stack.isEmpty())
	{
	    char top = stack.pop();

	    int precedence_old;
	    if (top == '+' || top == '-')
	    {
		// Lowest precedence
		precedence_old = 1;
	    }
	    else
	    {
		// Highest precedence
		precedence_old = 2;
	    }

	    if (precedence_old < precedence_new)
	    { 
		// Newer character has higher precedence
		stack.push(top);
		
		break;
	    }
	    else
	    {
		output = output + top;
	    }
	}
	
	stack.push(in);
    }
    
    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) 
    {	
	System.out.println("Infix is: " + input);
	
	for (int i = 0; i < input.length(); i++) 
	{
	    char c = input.charAt(i);
	    switch (c) 
	    {
		case '+': 
		case '-':
		    operator(c, 1); 
		    break;
		
		case '*':
		case '/':
		    operator(c, 2);
		    break;
		
		default:
		    output = output + c;
		    break;
	    }
	}
	
	while (!stack.isEmpty()) 
	{
	    output = output + stack.pop();
	}
	
	System.out.println("Postfix is: " + output);
    }

}

package p4;
// Oppgave 4.2
import java.util.Stack;
public class oppgave42{
    public static void remove(Stack<Integer> S1){
    	// Oppdretter et stack objekt
        Stack<Integer> S2 = new Stack<Integer>();
        // Finner ut hvor mange elemter det er i stack'en
        int holder = S1.size();
        for (int i = 0; i < holder; i++){
        	// Finner ut hva det øverste elementet er uten å fjerne det 
            if ((S1.peek() % 2) == 1){
                // Deler elementet på 2, hvis det blir 1 i rest så legges det til
            	S2.addElement(S1.pop());
            }
            else {
            // Fjerner det elementet
            S1.pop();
            }
        }
        holder = S2.size();
        for (int i = 0; i < holder; i++){
        	S1.addElement(S2.pop());
        }
    }
// Kjører programmet
    public static void main(String[] args){
	Stack<Integer> run = new Stack<Integer>();  
	for (int i = 0; i < 7; i++){
	    run.addElement(i);
	}
        remove(run);  
        System.out.println("utkrift " + run);
    }
}

package p4;
public class oppgave43 {
    boolean sjekk(String text){
	// Setter boolean verdien
	boolean statement = false;
	// returnerer plassen til C i text strengen
	int c = text.indexOf('C');
	// Lager en substreng for alt for og bak C
	String prefix = text.substring(0, c);
	String suffix = text.substring(c + 1);
	// Får alt bak C baklengs slik at vi sjekke om  de er like
	String suffixrev = new StringBuffer(suffix).reverse().toString();
	// Lager en IF setning som returnerer false or true om alt bak C er likt det foran
	if (prefix.equals( suffixrev ) ? statement = true : statement == false);
	return statement;
    }
    public static void main(String[] args){
    	oppgave43 run = new oppgave43();
    	if (run.sjekk("ABABBACABBABA") == true) {
		System.out.println("TRUE");
    	}
    	else {
		System.out.println("FALSE");
    	}
    } 
}

package p4;
class Stack {
    private int maxSize;
    private char[] stackArray;
    private int top;
    public Stack(int max) {
      maxSize = max;
      stackArray = new char[maxSize];
      top = -1;
    }
    public void push(char i) {
      stackArray[++top] = i;
    }
    public char pop() {
      return stackArray[top--];
    }
    public char peek() {
      return stackArray[top];
    }
    public boolean isEmpty() {
      return (top == -1);
    }
  }
public class oppgave45 {
  private Stack stack;
  private String input;
  private String output = "";
  public oppgave45() {
    String input = "1+2*4/5-7+3/6";
    int stackSize = input.length();
    stack = new Stack(stackSize);
  }
  public String convert() {
    for (int j = 0; j < input.length(); j++) {
      char character = input.charAt(j);
      switch (character) {
      case '+': 
      case '-':
        Operand(character, 1); 
        break; //   precedence 1
      case '*': //  * eller /
      case '/':
        Operand(character, 2); // pop 
        break; //   precedence 2
      default: // operand
        output = output + character; // Skriv ut
        break;
      }
    }
    while (!stack.isEmpty()) {
      output = output + stack.pop();
    }
    System.out.println(output);
    return output; // returner postfix
  }
  public void Operand(char opThis, int precedence1) {
    while (!stack.isEmpty()) {
      char opTop = stack.pop();
        int precedence2;
        if (opTop == '+' || opTop == '-')
          precedence2 = 1;
        else
          precedence2 = 2;
        if (precedence2 < precedence1) // hvis precedence ny eller mindre
        {
          stack.push(opTop); // lagre
          break;
        } else
          output = output + opTop;
      }
    stack.push(opThis);
  }
  public static void main(String[] args) {
    String output;
    oppgave45 theCon = new oppgave45();
    output = theCon.convert(); 
    System.out.println("Postfix er " + output + '\n');
  }
 
}