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(" "))))
}
}
:~/Workspace/scala$ fsc RPNCalc.scala :~/Workspace/scala$ scala RPNCalc 5 1 2 + 4 * 3 - + exp=14.00 19 2.14 + 4.5 2 4.3 / - * exp=85.30
And now some short explanations:
| RPNCalc is called a singleton object . I believe this is the official Scala “work-around” for defining static utilities functions . Anyways, pretty elegant for an work-around (being ironic) . |
ops is HashMap-like data-structure that maps a given string (in our case operators “+”, “-”, “*”, “/”) with an associated function literal . Thus we can use the map’s elements just like “normal” functions, for example: ops(“+”)(1, 3) evaluates to 4 .You may wonder what’s with the : ((_:Double) + (_:Double)) syntax . This is a concise way of saying ((a:Double, b:Double) => a + b), so the ops can anytime be rewritten as:
val ops = Map("+" -> ((a:Double, b:Double) => a + b),
"-" -> ((a:Double, b:Double) => b - a),
"*" -> ((a:Double, b:Double) => a * b),
"/" -> ((a:Double, b:Double) => b / a))
|
| evalTokens(tokens: Array[String]) works exactly as described in the algorithm presentation, the only notable thing about it, is that it uses the mutable version of a Stack data structure . |
And in the main function:
Source.fromInputStream(System.in).getLines.foreach(l => function(l)) Is the same as saying:
Scanner sc = new Scanner(System.in);
while(sc.hasNext()){
function(sc.nextLine());
}
in Java (read line by line from standard input) . |
At a first glimpse the python implementation looks very similar to the Scala implementation . Still there are some subtle differences, as python doesn’t have all the functional characteristics, and the programming style is a little different .
#!/usr/bin/env python
# author: Andrei Ciobanu
# date: JAN 3, 2010
import sys
import re
# dictionary <operator> - <function>
OPS = {
'+' : (lambda x, y: x + y),
'-' : (lambda x, y: y - x),
'*' : (lambda x, y: x * y),
'/' : (lambda x, y: y / x)
}
def evalTokens(tokens):
''' Evaluate RPN expr (given as string of tokens) '''
stack = []
for token in tokens:
if token in OPS:
stack.append(OPS[token](stack.pop(), stack.pop()))
else:
stack.append(float(token))
return stack.pop()
if __name__=="__main__":
while True:
# Read line by line from stdin + tokenize line + evaluates line
tokens = re.split(" *", sys.stdin.readline().strip())
print tokens
if not tokens:
break
sys.stdout.write("exp=%2.2fn" % evalTokens(tokens))
This solution is probably the most verbose, as Java has the more strict and primitive syntax, when compared to its counterparts .
In this particular case I wanted to imitate the previous solutions: have a map (dictionary) with operators and the corresponding anonymous functions . Unfortunately Java doesn’t have support for such constructs (lambda functions, clojures, etc.), so I had to somehow find a work-around .
The first Java solution:
import java.util.HashMap;
import java.util.Map;
import java.util.LinkedList;
import java.util.Scanner;
public class RPNCalc {
// Helper interface needed to immitate anonymous functions
public static interface Operation {
public Double eval(Double e1, Double e2);
}
public static Map<String, Operation> OPS = new HashMap<String, Operation>();
static {
OPS.put("+", new Operation(){ public Double eval(Double e1, Double e2){ return e1 + e2; }});
OPS.put("-", new Operation(){ public Double eval(Double e1, Double e2){ return e2 - e1; }});
OPS.put("*", new Operation(){ public Double eval(Double e1, Double e2){ return e1 * e2; }});
OPS.put("/", new Operation(){ public Double eval(Double e1, Double e2){ return e2 / e1; }});
};
// Evaluate RPN expr (given as array of tokens)
public static Double eval(String[] tokens) {
LinkedList<Double> stack = new LinkedList<Double>();
for(String token : tokens) {
if (OPS.containsKey(token)) {
stack.push(OPS.get(token).eval(stack.pop(), stack.pop()));
}
else {
stack.push(Double.parseDouble(token));
}
}
return stack.pop();
}
// Main function
public static void main(String args[]) {
Scanner sc = new Scanner(System.in);
while(sc.hasNext()) {
String line = sc.nextLine();
System.out.println("exp=" + eval(line.split(" ")));
}
}
}
Ok, but having an inner interface + some anonymous classes is a little overkill for our particular case . Maybe a more natural approach for Java would be to use functions instead:
import java.util.HashMap;
import java.util.Map;
import java.util.LinkedList;
import java.util.Scanner;
public class RPNCalc2 {
// List of supported operators
public static final String[] OPERATORS = { "+", "-", "*", "/" };
// Test if a token is operator
public static Boolean isOperator(String token) {
for(String op : OPERATORS) {
if(op.equals(token)) {
return true;
}
}
return false;
}
// Operation based on operator
public static Double operation(String op, Double e1, Double e2) {
if(op.equals("+")) {
return e1 + e2;
}
else if(op.equals("-")) {
return e2 - e1;
}
else if(op.equals("*")) {
return e1 * e2;
}
else if(op.equals("/")) {
return e2 / e1;
} else {
throw new IllegalArgumentException("Invalid operator.");
}
}
// Evaluate RPN expr (given as array of tokens)
public static Double eval(String[] tokens) {
LinkedList<Double> stack = new LinkedList<Double>();
for(String token : tokens) {
if (isOperator(token)) {
stack.push(operation(token, stack.pop(), stack.pop()));
}
else {
stack.push(Double.parseDouble(token));
}
}
return stack.pop();
}
// Main function
public static void main(String args[]) {
Scanner sc = new Scanner(System.in);
while(sc.hasNext()) {
String line = sc.nextLine();
System.out.println("exp=" + eval(line.split(" ")));
}
}
}
Conclusions:
Every language has its strength and weaknesses . Python is easy to learn, to read, to write and more important is fun . Java is verbose, but fast, and Scala, Scala is something new .
If you have any suggestions don’t hesitate to comment .
You may find interesting the following article: Shunting Yard Algorithm (how to convert infix expressions to Reverse Polish Notation).
Pingback: RPN Calculator (using Haskell) « andreINC.net