RPN Calculator (using Scala, python and Java)
One of the earliest Programming Praxis challenges is called RPN Calculator . Our task is to write a RPN module capable of evaluating simple RPN expressions and return the right result . The exact requirment:
Implement an RPN calculator that takes an expression like
19 2.14 + 4.5 2 4.3 / - *which is usually expressed as(19 + 2.14) * (4.5 - 2 / 4.3)and responds with 85.2974. The program should read expressions from standard input and print the top of the stack to standard output when a newline is encountered. The program should retain the state of the operand stack between expressions.Programming Praxis
The natural algorithm to resolve this exercise is stack-based :
| The first step is to tokenize the expression .If the expression is “19 2.14 + 4.5 2 4.3 / – *” after the tokenization the resulting structure will be an array of operands and operators, for example an array of Strings {“19”, “2.14”, “+”, “4.5”, “2”, “4.3”, “/”, “-“, “*”} . |
At the second step we iterate over the array of tokens .If the token:
|
| If the RPN expression is valid, after we apply the previous steps, the stack would contain only one value, which is the result of the calculation . |
I will implement the solutions for this challenge using three different languages: Scala, python and Java .
import scala.collection.mutable.Stack
import scala.io.Source
import java.lang.Double.parseDouble
/**
* RPN Calculator .
*
* @author Andrei Ciobanu
* @date JAN 2, 2011
**/
object RPNCalc {
// Maps an operator to a function .
val ops = Map("+" -> ((_:Double) + (_:Double)),
"-" -> (-(_:Double) + (_:Double)),
"*" -> ((_:Double) * (_:Double)),
"/" -> (1/(_:Double) * (_:Double)))
// Evaluate RPN expr (given as string of tokens)
def evalTokens(tokens: Array[String]) : Double = {
val stack = new Stack[Double]
tokens.foreach(tok => {
if (ops.contains(tok)) stack.push(ops(tok)(stack.pop, stack.pop))
else stack.push(parseDouble(tok))
})
stack.pop
}
// Main function
def main(args: Array[String]) = {
// Read line by line from stdin + tokenize line + evaluates line
Source.fromInputStream(System.in).getLines.foreach(l =>
printf("exp=%2.2fn", evalTokens(l.split(" "))))
}
}