This is a program which acts as a reverse polish notation calculator, there are two versions, one using Linked Lists, the other uses Arrays.
Example 4.2. Advanced Kenya Features Example - With Linked Lists.
/**
* Tristan Allwood (toa02 AT doc.ic.ac.uk)
* Reverse Polish Notation calculator example in Kenya
* Demonstrating enumerated types, generics, autoboxing
*
* This version uses Linked-List based stacks.
*
* Input on std input an RPN calculation (e.g.
* 1 2 + 3 * means 1 + 2 * 3
* 4 2 / means 4 / 2
* and on std out printed is the result ( e.g. 9 and 2 above ).
* Error cases are not handled gracefully here, esp no input = crash.
* Operators are +, -, *, /, % everything else that is not a number [0-9] is
* interpreted as ignorable whitespace.
*/
/**
* Program entry point, prints a welcome and then calls necessary methods
* to run the program
*/
void main(){
//Print a welcome
println("Welcome to the calculator!");
println("Please enter a calculation to be performed in reverse polish notation");
//Build the stacks of numbers and operators
Pair<Stack<int>,Stack<Operator>> stacks = buildStacks();
//Calculate the result from these
int result = mainLoop(stacks.b,stacks.a);
//Print out the result
println( "The answer is: " + result );
}
/**
* An enumeration of the Operators / Elements of the processed input stack.
* Number means that that element is a number ( found in the numbers stack )
*/
enum Operator{
Plus, Minus, Times, Divide, Modulo, Number;
}
/**
* Processes a stack of operators and a stack of numbers and uses them
* to calculate the result of the calculation.
*/
int mainLoop( Stack<Operator> operators, Stack<int> numbers ){
Stack<int> tmpNums;
while( hasNext(operators) ){
Operator op = pop(operators);
if ( op == Operator.Number ) {
push( tmpNums, pop(numbers) );
} else {
int snd = pop(tmpNums);
int fst = pop(tmpNums);
switch( op ) {
case Plus:{
push(tmpNums, fst + snd);
break;
}
case Minus:{
push(tmpNums, fst - snd);
break;
}
case Times:{
push( tmpNums, fst * snd);
break;
}
case Divide:{
push( tmpNums, fst / snd);
break;
}
case Modulo:{
push( tmpNums, fst % snd );
break;
}
}
}
}
return pop(tmpNums);
}
/**
* Builds the safer Stacks of operators and ints by parsing standard input.
*/
Pair< Stack<int>, Stack<Operator> > buildStacks(){
Stack<int> numStack;
Stack<Operator> wholeStack;
Stack<char> inputStack = getInputStack();
for( char c = pop(inputStack) ; hasNext( inputStack ) ; c = pop(inputStack) ){
if( '0' <= c & c <= '9' ){
push( inputStack, c );
int value = readNumber( inputStack );
push(numStack, value );
push(wholeStack, Operator.Number );
} else {
switch( c ){
case '+':{
push( wholeStack, Operator.Plus );
break;
}
case '-':{
push( wholeStack, Operator.Minus );
break;
}
case '/':{
push( wholeStack, Operator.Divide );
break;
}
case '*':{
push( wholeStack, Operator.Times );
break;
}
case '%':{
push( wholeStack, Operator.Modulo );
break;
}
default:{
/* any other letter is just ignored */
}
}//switch
} //else
}//for
Pair< Stack<int>, Stack<Operator> > retVal;
reverseStack(numStack);
reverseStack(wholeStack);
retVal.a = numStack;
retVal.b = wholeStack;
return retVal;
}//method
/**
* Converts a number representation on the stack (e.g. [1,2,3] )
* into its real value ( 123 )
*/
int readNumber( Stack<char> source ){
int number = 0;
char c = pop(source);
while( '0' <= c & c <= '9' ){
number = number * 10 + ( c - '0' );
c = pop(source);
}
push( source , c );
return number;
}
/**
* Turns standard input into a stack of characters.
*/
Stack<char> getInputStack(){
Stack<char> theStack;
for( char c = read() ; c != toChar(-1) ; c = read() ){
push(theStack, c);
}
reverseStack(theStack);
return theStack;
}
/* -------------------------- */
/* *** Pair utility class *** */
/* -------------------------- */
class Pair<T,Q> {
T a;
Q b;
}
/* ----------------------------------------- */
/* *** General Stack Library Stuff Below *** */
/* ----------------------------------------- */
/**
* Reverses the given stack.
*/
<T> void reverseStack( Stack<T> stack){
Stack<T> out;
while( hasNext(stack) ){
push( out, pop(stack) );
}
stack.head = out.head;
}
/**
* Prints out the given stack.
*/
<T> void printStack(Stack<T> stack){
LinkedList<T> top = stack.head;
print("[ " );
while( top != null ) {
print( top.node + " ");
top = top.next;
}
print("]");
}
/**
* Returns true iff the given stack has a "next" element
*/
<T> boolean hasNext( Stack<T> stack ){
return stack.head != null;
}
/**
* pushes a value onto the top of the given stack
*/
<T> void push( Stack<T> stack, T value ){
LinkedList<T> top;
top.node = value;
top.next = stack.head;
stack.head = top;
}
/**
* pops a value off the top of a given stack
*/
<T> T pop( Stack<T> stack ){
T value = stack.head.node;
stack.head = stack.head.next;
return value;
}
/**
* A Stack class ( holds a pointer to a LinkedList )
*/
class Stack<T>{
LinkedList<T> head;
}
/**
* A LinkedList class ( used to back a Stack )
*/
class LinkedList<T>{
LinkedList<T> next;
T node;
}
Example 4.3. Advanced Kenya Features - With Arrays
/**
* Tristan Allwood (toa02 AT doc.ic.ac.uk)
* Reverse Polish Notation calculator example in Kenya
* Demonstrating enumerated types, generics, autoboxing
*
* This version uses Array based stacks.
*
* Input on std input an RPN calculation (e.g.
* 1 2 + 3 * means 1 + 2 * 3
* 4 2 / means 4 / 2
* and on std out printed is the result ( e.g. 9 and 2 above ).
* Error cases are not handled gracefully here, esp no input = crash.
* Operators are +, -, *, /, % everything else that is not a number [0-9] is
* interpreted as ignorable whitespace.
*/
const int BUFFER_SIZE = 30; // how big a buffer to use for the arrays.
/**
* Program entry point, prints a welcome and then calls necessary methods
* to run the program
*/
void main(){
//Print a welcome
println("Welcome to the calculator!");
println("Please enter a calculation to be performed in reverse polish notation");
//Build the stacks of numbers and operators
Pair<Stack<int>,Stack<Operator>> stacks = buildStacks();
//Calculate the result from these
int result = mainLoop(stacks.b,stacks.a);
//Print out the result
println( "The answer is: " + result );
}
/**
* An enumeration of the Operators / Elements of the processed input stack.
* Number means that that element is a number ( found in the numbers stack )
*/
enum Operator{
Plus, Minus, Times, Divide, Modulo, Number;
}
/**
* Processes a stack of operators and a stack of numbers and uses them
* to calculate the result of the calculation.
*/
int mainLoop( Stack<Operator> operators, Stack<int> numbers ){
Stack<int> tmpNums = newStack( new Integer[BUFFER_SIZE]);
while( hasNext(operators) ){
Operator op = pop(operators);
if ( op == Operator.Number ) {
push( tmpNums, pop(numbers) );
} else {
int snd = pop(tmpNums);
int fst = pop(tmpNums);
switch( op ) {
case Plus:{
push(tmpNums, fst + snd);
break;
}
case Minus:{
push(tmpNums, fst - snd);
break;
}
case Times:{
push( tmpNums, fst * snd);
break;
}
case Divide:{
push( tmpNums, fst / snd);
break;
}
case Modulo:{
push( tmpNums, fst % snd );
break;
}
}
}
}
return pop(tmpNums);
}
/**
* Builds the safer Stacks of operators and ints by parsing standard input.
*/
Pair< Stack<int>, Stack<Operator> > buildStacks(){
Stack<int> numStack = newStack( new Integer[ BUFFER_SIZE] );
Stack<Operator> wholeStack = newStack( new Operator[BUFFER_SIZE] );
Stack<char> inputStack = getInputStack();
for( char c = pop(inputStack) ; hasNext( inputStack ) ; c = pop(inputStack) ){
if( '0' <= c & c <= '9' ){
push( inputStack, c );
int value = readNumber( inputStack );
push(numStack, value );
push(wholeStack, Operator.Number );
} else {
switch( c ){
case '+':{
push( wholeStack, Operator.Plus );
break;
}
case '-':{
push( wholeStack, Operator.Minus );
break;
}
case '/':{
push( wholeStack, Operator.Divide );
break;
}
case '*':{
push( wholeStack, Operator.Times );
break;
}
case '%':{
push( wholeStack, Operator.Modulo );
break;
}
default:{
/* any other letter is just ignored */
}
}//switch
} //else
}//for
Pair< Stack<int>, Stack<Operator> > retVal;
reverseStack(numStack);
reverseStack(wholeStack);
retVal.a = numStack;
retVal.b = wholeStack;
return retVal;
}//method
/**
* Converts a number representation on the stack (e.g. [1,2,3] )
* into its real value ( 123 )
*/
int readNumber( Stack<char> source ){
int number = 0;
char c = pop(source);
while( '0' <= c & c <= '9' ){
number = number * 10 + ( c - '0' );
c = pop(source);
}
push( source , c );
return number;
}
/**
* Turns standard input into a stack of characters.
*/
Stack<char> getInputStack(){
Stack<char> theStack = newStack( new Character[BUFFER_SIZE] );
for( char c = read() ; c != toChar(-1) ; c = read() ){
push(theStack, c);
}
reverseStack(theStack);
return theStack;
}
/* -------------------------- */
/* *** Pair utility class *** */
/* -------------------------- */
class Pair<T,Q> {
T a;
Q b;
}
/* ----------------------------------------- */
/* *** General Stack Library Stuff Below *** */
/* ----------------------------------------- */
/**
* Since in generics you can't create an array of
* Template type at runtime, you have to provide
* the backing buffer when you create a new Stack.
* This is a method that emulates the constructor.
*/
<T> Stack<T> newStack( T[] backBuffer ){
Stack<T> newStack;
newStack.store = backBuffer;
return newStack;
}
/**
* Reverses the given stack.
*/
<T> void reverseStack( Stack<T> stack){
T[] array = stack.store;
int max = stack.cPos - 1;
for( int i = 0 ; i < max ; i++ ){
T tmp = array[i];
array[i] = array[max];
array[max] = tmp;
max--;
}
}
/**
* Prints out the given stack.
*/
<T> void printStack(Stack<T> stack){
print("[ ");
for( int i = 0 ; i < stack.cPos ; i++ ){
print( stack.store[i] + " " );
}
println("]");
}
/**
* Returns true iff the given stack has a "next" element
*/
<T> boolean hasNext( Stack<T> stack ){
return stack.cPos > 0;
}
/**
* pushes a value onto the top of the given stack
*/
<T> void push( Stack<T> stack, T value ){
stack.store[stack.cPos] = value;
stack.cPos++;
}
/**
* pops a value off the top of a given stack
*/
<T> T pop( Stack<T> stack ){
stack.cPos--;
T value = stack.store[stack.cPos];
stack.store[stack.cPos] = null; // just for safety
return value;
}
/**
* A Stack class
*/
class Stack<T>{
T[] store;
int cPos;
}