Dæmi 1 (2 stig)

Takið upphaflega RPN forritið sem var sýnt í fyrirlestri og breytið því á eftirfarandi hátt.

Aðgerðir eiga að vera strengir ("+", "*", "p") en ekki bókstafir ('+', '*', 'p'). Það á að vera hægt að bæta inn aðgerð sem inniheldur fleiri en einn bókstaf, t.d. "drop". Gerið tilheyrandi breytingar á struct operation, operations og eval_op.
Bætið við nýrri skipun "drop" sem fleygir burt efsta stakinu af hlaðanum.
Bætið við nýrri skipun "dup" sem tekur efsta stakið á hlaðanum og setur það tvisvar á hlaðann (duplicate top value).
Bætið við nýrri skipun "swap" sem víxlar tveimur efstu stökunum á hlaðanum.

rpn.c

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "stack.h"

const char delim[] = " \n";

static int is_number(char *s)
{
	return strspn(s, "1234567890") == strlen(s);
}

static void eval_plus(struct stack *s)
{
	int a, b;

	a = stack_pop(s);
	b = stack_pop(s);

	stack_push(s, a + b);
}

static void eval_multiply(struct stack *s)
{
	int a, b;

	a = stack_pop(s);
	b = stack_pop(s);

	stack_push(s, a * b);
}

static void eval_drop(struct stack *s)
{
	stack_pop(s);
}

static void eval_dup(struct stack *s)
{
	int v = stack_pop(s);

	stack_push(s, v);
	stack_push(s, v);
}

static void eval_swap(struct stack *s)
{
	int a, b;

	a = stack_pop(s);
	b = stack_pop(s);

	stack_push(s, a);
	stack_push(s, b);
}

struct operation
{
	char *op;
	int minargs;
	void (*eval)(struct stack *s);
};

static struct operation operations[] =
{
	{ "+", 2, eval_plus },
	{ "*", 2, eval_multiply },
	{ "p", 0, stack_print },
	{ "drop", 1, eval_drop },
	{ "dup", 1, eval_dup },
	{ "swap", 2, eval_swap },
	{ 0, 0, NULL }
};

static void eval_op(struct stack *s, char *token)
{
	struct operation *op;

	for (op = operations; op->eval; op++)
	{
		if (!strcmp(op->op, token))
			break;
	}

	if (op->eval == NULL)
	{
		printf("Unknown operation: %s\n", token);
		return;
	}

	if (stack_count(s) < op->minargs)
	{
		printf("Not enough arguments on stack\n");
		return;
	}

	op->eval(s);
}

void eval(struct stack *s, char *line)
{
	char *state = line;
	char *token;

	token = strtok_r(line, delim, &state);

	while (token != NULL)
	{
		printf("token: %s\n", token);

		if (is_number(token))
			stack_push(s, atoi(token));
		else
			eval_op(s, token);

		token = strtok_r(NULL, delim, &state);
	}
}

int main(void)
{
	char line[1024];
	struct stack s;

	stack_init(&s);

	while (1)
	{
		if (feof(stdin) || ferror(stdin))
			break;

		if (fgets(line, sizeof(line), stdin) == NULL)
			break;

		eval(&s, line);
	}

	return 0;
}

stack.c

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "stack.h"

void stack_init(struct stack *s)
{
	s->top = NULL;
	s->n = 0;
}

void stack_push(struct stack *s, int value)
{
	struct item *p = malloc(sizeof(struct item));

	p->value = value;
	p->next = s->top;
	s->top = p;
	s->n++;
}

int stack_pop(struct stack *s)
{
	struct item *p = s->top;
	int value = p->value;

	s->top = s->top->next;
	s->n--;

	free(p);

	return value;
}

int stack_empty(struct stack *s)
{
	return s->top == NULL;
}

int stack_count(struct stack *s)
{
	return s->n;
}

void stack_print(struct stack *s)
{
	struct item *p = s->top;

	printf("Stack (from top to bottom):\n");

	while (p != NULL)
	{
		printf("  [%d]\n", p->value);
		p = p->next;
	}
}

int stack_top(struct stack *s)
{
	return s->top->value;
}

stack.h

#ifndef _STACK_H
#define _STACK_H

struct item
{
	int value;
	struct item *next;
};

struct stack
{
	struct item *top;
	int n;
};

extern void stack_init(struct stack *s);
extern void stack_push(struct stack *s, int value);
extern int stack_empty(struct stack *s);
extern int stack_count(struct stack *s);
extern void stack_print(struct stack *s);
extern int stack_pop(struct stack *s);
extern int stack_top(struct stack *s);

#endif

Dæmi 2 (2 stig)

Leysið dæmi 1.3.4 í bókinni í Java. Notið Stack klasann úr fyrirlestri.

Write a stack client Parentheses in Java that reads in a text stream from standard input and uses a stack to determine whether its parentheses are properly balanced. For example, your program should print true for [()]{}{[()()]()} and false for [(]).

Prófun

Inntak:

[()]{}{[()()]()}
[(])

Úttak:

true
false

Parentheses.java

import java.util.Scanner;

public class Parentheses
{
	private static char flip(char c)
	{
		switch (c)
		{
			case ')':
				return '(';
			case '}':
				return '{';
			case ']':
				return '[';
		}

		return '?';
	}

	public static boolean balanced(String line)
	{
		Stack<Character> s = new Stack<Character>();

		for (int i = 0; i < line.length(); i++)
		{
			char c = line.charAt(i);

			if (c == '(' || c == '{' || c == '[')
			{
				s.push(c);
				continue;
			}

			if (s.empty())
				return false;

			char top = s.pop();

			if (top != flip(c))
				return false;
		}

		return true;
	}

	public static void main(String[] args)
	{
		Scanner s = new Scanner(System.in);

		while (s.hasNext())
		{
			String line = s.nextLine();

			if (balanced(line))
				System.out.println("true");
			else
				System.out.println("false");
		}
	}
}

Dæmi 3 (3 stig)

Takið upphaflega RPN forritið (rpn.zip) sem var sýnt í fyrirlestri og forritið hliðstæða útgáfu í Java. Forritið á að hegða sér nákvæmlega eins og C forritið. Notandi forritsins ætti ekki að geta sagt til um hvort forritið hann er að keyra.

Prófun

2
token: 2
3
token: 3
4
token: 4
5
token: 5
p
token: p
Stack (from top to bottom):
  [5]
  [4]
  [3]
  [2]
+
token: +
*
token: *
+
token: +
p
token: p
Stack (from top to bottom):
  [29]

RPN.java

import java.util.Scanner;

public class RPN
{
	private static boolean isNumeric(String w)
	{
		try
		{
			Integer.parseInt(w);
		} catch (NumberFormatException e)
		{
			return false;
		}

		return true;
	}

	public static void main(String[] args)
	{
		Stack<Integer> s = new Stack<Integer>();
		Scanner scan = new Scanner(System.in);

		while (scan.hasNext())
		{
			String w = scan.next();

			System.out.printf("token: %s\n", w);

			if (isNumeric(w))
			{
				s.push(Integer.parseInt(w));
				continue;
			}

			if (w.equals("+"))
			{
				if (s.count() < 2)
				{
					System.out.println("Not enough arguments on stack");
					continue;
				}

				s.push(s.pop() + s.pop());

			} else if (w.equals("*"))
			{
				if (s.count() < 2)
				{
					System.out.println("Not enough arguments on stack");
					continue;
				}

				s.push(s.pop() * s.pop());

			} else if (w.equals("p"))
			{
				System.out.println("Stack (from top to bottom)");
				s.print();
			} else
			{
				System.out.printf("Unknown operation: %s\n", w);
			}
		}
	}
}

Stack.java

public class Stack<T>
{
	class Node
	{
		T value;
		Node next;
	};

	private Node top;
	private int n;

	Stack()
	{
		top = null;
		n = 0;
	}

	public void push(T value)
	{
		Node x = new Node();
		x.value = value;
		x.next = top;
		top = x;
		n++;
	}

	public T pop()
	{
		T x = top.value;
		top = top.next;
		n--;
		return x;
	}

	public T peek()
	{
		return top.value;
	}

	public boolean empty()
	{
		return top == null;
	}

	public void print()
	{
		Node p = top;

		while (p != null)
		{
			System.out.printf("  [%s]\n", p.value);
			p = p.next;
		}
	}

	public int count()
	{
		return n;
	}

	public static void main(String[] args)
	{
		Stack<String> s = new Stack<String>();

		s.push("A");
		s.push("B");
		s.push("C");

		while (!s.empty())
			System.out.println(s.pop());
	}
}

Dæmi 4 (3 stig)

Klárið útfærslu af walktree fallinu í beinagrindinni. Fallið tekur inn skrá/möppu (File object) og FileVisitor hlut. Fallið gengur yfir allar skrár og möppur sem liggja undir slóðinni og fyrir hverja skrá/möppu þá er kallað á visit í FileVisitor.

Forritið á að nota hlaða, sem fylgir með beinagrindinni. Forritið tekur næstu skrá af hlaðanum, kallar á FileVisitor og síðan kallar það á listFiles á viðkomandi skrá, sem sækir allar undirskrár/undirmöppur, og setur allar undirskrár/undirmöppur á hlaðann.

Walker.java

import java.io.File;

interface FileVisitor
{
	void visit(File file);
}

public class Walker
{
	static class PrintFile implements FileVisitor
	{
		public void visit(File file)
		{
			if (file.isDirectory())
				System.out.printf("D %s\n", file.getAbsolutePath());
			else
				System.out.printf("F %s (%d bytes)\n", file.getAbsolutePath(), file.length());
		}
	}

	public static void walktree(File root, FileVisitor visitor)
	{
		Stack<File> s = new Stack<File>();
		s.push(root);

		while (!s.empty())
		{
			File f = s.pop();

			visitor.visit(f);

			File[] files = f.listFiles();

			if (files == null)
				continue;

			for (File cf : files)
				s.push(cf);
		}
	}

	public static void main(String[] args)
	{
		if (args.length < 1)
		{
			System.err.println("usage: java Walker <path>");
			return;
		}

		File root = new File(args[0]);

		walktree(root, new PrintFile());
	}
}

Stack.java

public class Stack<T>
{
	class Node
	{
		T value;
		Node next;
	};

	private Node top;
	private int n;

	Stack()
	{
		top = null;
		n = 0;
	}

	public void push(T value)
	{
		Node x = new Node();
		x.value = value;
		x.next = top;
		top = x;
		n++;
	}

	public T pop()
	{
		T x = top.value;
		top = top.next;
		n--;
		return x;
	}

	public T peek()
	{
		return top.value;
	}

	public boolean empty()
	{
		return top == null;
	}

	public int count()
	{
		return n;
	}

	public static void main(String[] args)
	{
		Stack<String> s = new Stack<String>();

		s.push("A");
		s.push("B");
		s.push("C");

		while (!s.empty())
			System.out.println(s.pop());
	}
}

Tölvunarfræði 2 - Vor 2012

Verkefni 4 - Sýnislausn

Dæmi 1 (2 stig)

rpn.c

stack.c

stack.h

Dæmi 2 (2 stig)

Prófun

Parentheses.java

Dæmi 3 (3 stig)

Prófun

RPN.java

Stack.java

Dæmi 4 (3 stig)

Walker.java

Stack.java