PLACE |
spec |
solutions |
Eiffel |
As Eiffel is a purely object-oriented, class-based language, in the following program the RPN calculator's logic is implemented within a procedure that is a member of a class. The procedure is given the name make
, which by a popular convention is the name for an instance creator (constructor) for a class. That that procedure really is a constructor is due to the create
specifier given in the first line of the program. The class's name is rpn
, and so is that of the resulting executable program. By definition, running the program means running the constructor of the class, thus executing the calculator.
Besides make
there are two other features (the Eiffel word for members) defined in the class. The content within the curly braces accompanying a feature
clause indicates the scope of visibility of the names that follow. Since none
and any
are the bottommost and the topmost classes in Eiffel's class taxonomy, make
is potentially accessible from any other class that may be present in the program, while the other two features are seen from nowhere else, therefore for private use within the class only. Of course, in this particular program the mentioned distinction is not important, but it does make good sense when the class is a part of a larger program.
The calculator mainly consists of a loop of the form – and this is the only available form of explicit iteration in the language – from
-until
-loop
-end
. The initializing from
part creates an empty stack st
and a sort of traversable string object sq
, also empty, though this is unimportant – that string's contents are initialized later, but the sq
's creator still requires an argument. Note that st
and sq
are precisely the two private features of the class. For reasons that will become clear below, they cannot be declared as entities, local to make
, in spite of the latter seeming to be a more reasonable thing to do.
The main part of the loop – the one after the word loop
– reads lines from the standard input and processes them, which it does apparently until the input gets exhausted (end_of_file
returns true).
A just read line is accessible as the value of the io.laststring
, but that appears to be a too simple kind of string in Eiffel: in a sense, its contents cannot be considered an ordered sequence. To achieve ‘linearization’, and thus traversability, we fill the contents of sq
, of class seq_string
, with those of io.laststring
; in fact, the characters are shared between the two kinds of strings, not copied. Now that sq
is initialized properly, the do_all
method acts on it with an inline ‘agent’ as an argument. Do_all
's job is to call the agent once for each character in sq
. This agent checks if a character is a tab, and if so replaces it with a space.
Eiffel's agents are objects representing procedures. (We need a value to pass to do_all
, and all values are objects, but procedures are not objects. Hence agents are needed to make the transition between the two.) Inline agents are like anonymous procedures. Thus, through agents, there is a restricted provision for functional programming in the language. Do_all
, in particular, is one of the library-provided functional-style iterators over a sequence, typically making use of agents.
The final thing to do with sq
, which is the slightly modified input line, is to transform it into a list of tokens tks
by calling split
on it. Split
, by the way, only allows a single character as a delimiter. We want to accept tab characters as delimiters, too, that is why we had to change all tabs in sq
to spaces, and actually only use a space as a delimiter passed to split
.
Tks
, itself being a sequence, is acted upon by another do_all
, passing the latter an inline agent, responsible for processing a single token.
The agent, to which the current token is known as its parameter tk
, does nothing if tk
is an empty string (empty strings will be present in tks
when there are leading spaces or sequences of more than one space elsewhere in sq
). If tk
happens to represent a number, that number gets pushed on the stack st
. If, instead, tk
is an operator, the respective arithmetic operation is performed on the topmost two items of st
and the result is put on st
in their place. Once do_all
is done, it only remains to check if the stack is non-empty, showing the input line was not empty, and if it contains a single number, that one is printed and removed from st
. Out
produces the string representation of any value, in our case the number.
The possible syntax errors in the RPN expression are handled by raising exceptions. If an exception is raised, the rescue
part of the make
procedure is executed. There, an error message gets printed, and then the retry
statement causes make
to be restarted from its very beginning. The way the program can cause an exception to occur is by violating any of the two check
clauses (the first one itself consisting of two parts), as well as by not providing a default (else
) clause of the inspect
statement; by definition, if none of the explicit clauses of inspect
receives control and no else
is present, an exception is signaled.
It should be noted that Eiffel programs can be compiled without including code for assertions and for reacting on their possible violation. Because the calculator, as written and described, depends heavily on both (the specific kind of assertions in use being check
), the program only works correctly when compiled with assertions kept.
Observe that the two mentioned ‘agents’ refer to sq
and st
, correspondingly, in their bodies. As only local names defined in the immediately enclosing context are allowed in such bodies, these names could not have been defined local within make
: that would be one layer outer (the immediate context is that of the agent itself). That is why these two variables had to be made features of the class and not local variables.
The program makes use of a lot of library-defined classes and their features. All are members of the so called kernel library of the language.
A note on the resource consumption observed using the EiffelStudio 5.7 compiler for Eiffel (the one coming from the company headed by the author of the language) on a 1.7GHz machine. The program presented here compiled (under GNU/Linux) to an executable 784 kB large with assertion support dropped. The whole compilation and linking, including compiling and linking the generated C code, took about 45 sec. With assertions retained, the volume was 2,807 kB and the compilation took 3 min.
class Rpn create make feature {none} st: linked_stack[double] sq: seq_string feature {any} make is local tks: list[string] do from create st.make create sq.make(0) until io.input.end_of_file loop io.readline sq.make_from_string(io.laststring) sq.do_all(agent (c:character) do if c = '%T' then sq.replace(' ') end end) tks := sq.split(' ') tks.do_all( agent (tk:string) local x,y:double do if not tk.is_empty then if tk.is_double then st.put(tk.to_double) else check st.count > 1; tk.count = 1 end y := st.item; st.remove x := st.item inspect tk @ 1 when '+' then x := x+y when '-' then x := x-y when '*' then x := x*y when '/' then x := x/y end st.replace(x) end end end) if not st.is_empty then check st.count = 1 end print(st.item.out+"%N") st.remove end end rescue print("error%N") retry end end
boykobbatgmaildotcom