PLACE
spec
solutions
ABC

RPN Calculator in ABC

The program consists of a main portion and four how-to's (sub-programs). The ABC interpreter requires that, in the text, the how-to's are defined before being used. Accordingly, the main part is at the end, and the how-to's are so ordered that callers follow callees.

The main part does the trivial job of reading a line, s, from the standard input and passing it to the eval.rpn function. The outcome produced by the latter is stored in r (PUT…IN… is the assigning command of ABC), and if it is a non-empty string, it gets printed. A non-empty string contains either the image of a number resulting from a succesful RPN expression evaluation, or 'error' if the evaluation failed. The / tells WRITE to output an end-of-line character. The read-evaluate-print loop is infinite, because there is no means to detect when the input ends. (For actual program termination, one should make use of Ctrl-C or a similar interruption device.)

eval.rpn uses the split built-in function to break the input line down into a sequence of tokens, and then processes the individual tokens in order. A token, tk, is checked against the set (list) of arithmetic operator characters, and if it fails, another how-to, FIND OUT…, is called to try to evaluate it as a number. A stack, stk, is maintained for storing the intermediate values in the course of the expression evaluation. A token being neither an operator nor a number, and an operator for which there is no pair of arguments in the stack, both lead to immediately returning 'error' to the main program.

After processing thus all tokens (if any at all found) the stack should contain a single number – the result – and that number is also the value of x. So in this case the value returned by eval.rpn is the textual representation of x, which we obtain by making use of the ‘evaluating quotes’ (``) within the string-delimiting pair of quotes: '`x`'. For a stack of more than one number we return the 'error' string, and for an empty stack – meaning the input line was empty – an empty string is returned, in order for the main program to know that there is nothing to print.

Note that both the sequence of tokens and the stack are represented by associative tables. While using lists to represent sequential data structures may seem more appropriate, in fact lists are inapplicable here. ABC tacitly sorts the contents of a list, disrespecting the order in which they get there, and that is unacceptable for both the token sequence and the stack. On the other hand, an associative table with integer keys is not unlike an array and therefore does represent a linear structure, despite the fact that tables are non-sequential by nature. The split function creates precisely such a table, and consequentially the FOR loop traverses the tokens in the correct order. As for the stack, all we need to have it represented in the said kind of table is taking care to add new items under properly increasing subscripts (1+#stk, where #stk is the current number of items in stk), and popping off the item at the largest subscript (#stk).

Popping the stack off is implemented as a separate command POP OFF…INTO…. The popped item is stored in the command's second argument and removed from stk.

The FIND OUT… command analyzes a token, s, to see whether it reads as a number and, if so, finds out that number by the characters that make it up. ABC itself offers no direct means to do either of these (see also e.g. the Pascal and Smalltalk implementations in this respect). The number, if there is one, is stored in the command's second parameter, r. The third parameter, f, is given an empty string value when s does parse as a number. A (whatever) non-empty string signals an error to the caller; here, -- is used.

Within FIND OUT…, if there is an arithmetic sign (in a leading position) in s, it is removed, and sgn remembers a value of ±1. Then, a decimal dot is looked up in s by calling the index function. If one is present, it is also removed from the string, meanwhile computing a power (pow) of 10 that reflects the dot’s location within s. The string s at this point must be non-empty and only consist of digits; if not, an error is flagged to eval.rpn by setting f and the command's execution ends. The integer value remaining in a correctly formed string s is computed by sequentially traversing the digits in it. The thus obtained value is subjected to the necessary corrections, multiplying it by pow and sgn, and finally returned by setting r to it.

The expressions of the kinds s|… and s@… compute a prefix and a suffix of s with respect to a given location in it.

index is a two-argument function – such functions have infix syntax in ABC – that locates the first occurrence of a character e in a string t, returning the respective position or 0 if none is found. The search is expressed in terms of a SOME…IN…HAS… test form (also used in FIND OUT…. Note that, when the search succeeds, the ‘needle variable’ gets bound to the value that has been found. This is how RETURN can refer to that value in order to pass it to the caller.

HOW TO RETURN t index e:
  IF SOME i IN {1..#t} HAS t item i = e: RETURN i
  RETURN 0

HOW TO FIND OUT IS s A NUMBER r FAILING f:
  PUT '' IN f
  PUT 1 IN sgn
  IF s item 1 in {'+'; '-'}:
    IF s = '-': PUT -1 IN sgn
    PUT s@2 IN s
  PUT 1 IN pow
  PUT s index '.' IN i
  IF i > 0:
    PUT 10**(i-#s) IN pow
    PUT s|(i-1) ^ s@(i+1) IN s
  IF #s = 0 OR SOME c IN s HAS c not.in '0123456789':
    PUT '--' IN f
    QUIT
  PUT 0 IN r
  FOR c IN s:
    PUT 10*r+(('0123456789' index c) - 1) IN r
  PUT sgn*r*pow IN r

HOW TO POP OFF a INTO z:
  PUT a[#a] IN z
  DELETE a[#a]

HOW TO RETURN eval.rpn s:
  PUT {} IN stk
  FOR tk IN split s:
    SELECT:
      tk in {'+'; '-'; '*'; '/'}:
        IF #stk<2: RETURN 'error'
        POP OFF stk INTO y
        POP OFF stk INTO x
        SELECT:
          tk='+': PUT x+y IN x
          tk='-': PUT x-y IN x
          tk='*': PUT x*y IN x
          ELSE:   PUT x/y IN x
      ELSE:
        FIND OUT IS tk A NUMBER x FAILING err
        IF err <> '': RETURN 'error'
    PUT x IN stk[1+#stk]
  IF #stk = 1: RETURN '`x`'
  IF #stk > 1: RETURN 'error'
  RETURN ''

WHILE 0=0:   \ main program
  READ s RAW
  PUT eval.rpn s IN r
  IF r <> '': WRITE r /

boykobbatgmaildotcom