PLACE
spec
solutions
D

RPN Calculator in D

The following program is written in D2, the current (as of 2010) version of D and of its standard library Phobos.

The outer foreach loop reads lines from the standard input and assigns each one in turn to a string s. An internal foreach loop breaks s down (split) into tokens, and iterates over the resulting sequence by processing each token tk in it.

A dynamic array nums is being made use of for maintaining a stack of intermediate values in the course of evaluating an RPN expression. If a token happens to represent an arithmetic operator, that operator is applied to a pair of numbers pulled off the stack. Otherwise tk must parse as a number, and that number is obtained using the library function to. In both cases the result x gets pushed onto the stack.

Once all tokens are processed this way, the result x of evaluating the RPN expression is printed out. If the token sequence produced by split was actually empty, the inner foreach does nothing and consequently nums remains empty, so nothing is printed in this case.

nums is initially empty and gets cleared after processing each input line. Augmenting and reducing the stack is done by using the concatenation operator ~= and the function pop, respectively. Referencing and removing the last element of nums in pop makes use of standard library function calls.

The token processing and its epilogue are nested into a try–catch block so that possible syntax errors in the RPN expression can be caught. Such an error would cause an exception to be raised and eventually handled by printing out an error message. Clearing the stack is put in a finally clause in order to ensure that it takes place regardless of whether an exception occured or not.

An exception occurs in three different ways. One is within pop, when trying to reference an item in an empty nums. Another is within to, when a token tk does not read as a number. Exception is also being thrown explicitly when there is more than a single number left on the stack after the whole RPN expression is processed. The argument of throw is not used and therefore arbitrary, provided that it is an instance of the Exception class.

(The if–throw– part can be more tersely written assert(nums.length<=1). However, asserts are considered but a debugging tool which should not be active in a normal program, so much so that they can be deleted from the program by a compiler option. In other words, assert is considered a tool for detecting program errors, and not one for program control.)

Both loops in the program are abstract, in the sense that they are implicitly controlled by the sequences (ranges, in D's parlance) which they traverse. Thus, the inner loop does as many iterations as there are tokens, and the outer terminates as soon as there are no more lines to read.

As can be observed in this program, D is capable of inferring the types of program objects that depend on other program objects. For example, both ‘loop variables’ s and tk are strings, but this is deduced from the types of byLine and split rather than stated in the text. The type of t within pop, as well as the return type of pop itself, are also omitted (by writing the formal substitute auto instead) and automatically inferred from the element type of nums.

Apart from nums, the type double is given in two other places. In those places, rather than double, we could have written, e.g., typeof(nums[0]), meaning ‘the element type of nums’. That would probably be overkill for this particular program, but relative type specification is a useful device in general.

The function to is overloaded and templatized for many kinds of conversions between data types. The type of its argument, string (tk) in this case, selects among all instantiations of to the family that converts from string values. To pick up the specific instance within this family that produces doubles, to is also given a template argument: a type specification that precedes the value argument and is delimited from the function's name by !.

All standard library functions in D reside in modules, so accessing such functions requires either prefixing their names with those of the respective modules or importing the modules. Examples of both styles can be seen in the program. split and to are each used once, and both of them are the only representatives of their modules, so it seems reasonable to use fully-prefixed names and avoid importing the modules. On the other hand, empty, clear, back, and popBack all belong to the module std.array which justifies including it.

Including std.array has an additional benefit to making the text shorter and cleaner. A special convention allows the calls of array functions to be made syntactically the same as referring to array properties, such as length; so we use nums.back as a more convenient form of back(nums) etc. In turn, referencing a property is similar to calling a method, such as in stdin.byLine().

import std.stdio, std.array;

double[] nums;
auto pop() {auto t = nums.back; nums.popBack; return t;}

void main() {
  foreach (s; stdin.byLine())
    try {
      double x;
      foreach (tk; std.string.split(s)) {
        switch (tk) {
          case "+": x = pop()+pop(); break;
          case "*": x = pop()*pop(); break;
          case "-": x = pop(); x = pop()-x; break;
          case "/": x = pop(); x = pop()/x; break;
          default:  x = std.conv.to!double(tk);
        }
        nums ~= x;
      }
      if (nums.length>1) throw new Exception("");
      if (!nums.empty) writeln(x);
    }
    catch {writeln("error");}
    finally nums.clear;
}

boykobbatgmaildotcom