PLACE
spec
solutions
U

RPN Calculator in U

I give two versions of a calculator in U.

The first is iterative, making use of a stack of intermediate values. The program is an expression that processes a text line by passing it to an anonymous function. Within the function the line, s, is being split into a sequence tks of non-blank tokens. If non-empty, tks gets traversed left-to-right (>) applying evaltk. The resulting value is fed to result, so that either a string representing a number or the string "error is obtained, depending on the correctness of the initial input. That string is printed, and finally a new line is read, if available on the standard input. The result of calling readf becomes the result of the anonymous function. The built-in function beyond ensures that the anonymous function keeps being called while it, i.e. readf, returns a valid value, this being checked by calling val on that value.

evaltk takes a stack of numbers ns and a token tk. If tk successfully reads as a number, the variable x stores that number. Otherwise x is assigned the ‘non-value’ $. Similarly, if tk is equal to any of the one-character strings '+, '-, '*, and '/, op is assigned the respective operator, and $ otherwise. Also, xy gets the last two items of the sequence ns – the topmost two numbers of the stack – or $ if there are less than two in ns. x, op, and xy are local within a conditional expression. With all this preparation done, if x holds a non-$ value, that is appended to ns. Alternatively, if both op and xy are non-$, the operator stored in op acts on the two numbers in xy. The result is appended to ns after removing from the latter those two numbers still present in it.

If tk is neither a number nor an operator, or if ns has no (at least) two items when it has to, the conditional expression returns $, and so does evaltk. The subsequent calls to evaltk then will see $ as the value of ns, which leads to each of them also returning $.

It is ensured that ns is initially empty by appending [] in front of tks before calling >. Upon processing a correct RPN expression the result is a sequence of a single number – this is what result pattern-matches against.

@{[s] ::
  ?{tks<>[] :: '() write(evaltk > ([]\tks) | result / '('n))
  ++ tks = s split '( '#0009)
  ;  evaltk = @{[ns;tk] (val.ns) ::
       ?{val.x           :: ns/x
       ; &.(val![op;xy]) :: -2>ns/(op.xy)
       ++ x = tk reads["num] | @{[x;'()]::x}
       ;  op = [['+;+];['-;-];['*;*];['/;/]] assv tk
       ;  xy = 2>ns}}
  ;  result = @{[r] :: '() frm r; _ :: "error}}
  next ('() readf[])}
beyond val . '()

 

The next version is recursive, processing the token sequence tks backwards by the use of a recursive function evalrpn. A call of it takes a sequence of tokens containing at least one token tk. Similarly to the iterative version, that tk gets checked against being a number or an arithmetic operator.

If an operator, evalrpn is invoked on the remainder tks of the sequence. The alias @ for ‘the same function’ is used for that. The result is fed to an anonymous function so that, if the call was successful, the pattern [y;tks] matches, in effect producing a numeric value y and a shorter sequence tks. Then evalrpn is called again on this tks (here with the alias @@ because evalrpn is not the current but the enclosing function). The result of this call is fed to yet another anonymous function, where upon success the pattern [x;tks] matches, producing a number x and a still shorter sequence tks. Finally the result of applying op on x and y is paired with that tks as the value returned by evalrpn.

If tk fails to read as a number or an operator, the conditional expression, and consequently evalrpn, returns a $. The $ propagates upwards through the recursive calls as one of the anonymous functions nested within the conditional expression fails to match its argument against the pattern.

Eventually the topmost call of evalrpn returns either a pair of a number and an empty sequence or $. These two cases are mapped to a string value by ‘piping’ the result of evalrpn through result.

@{[s] ::
  ?{tks<>[] :: '() write(tks | evalrpn | result  / '('n))
  ++ tks = s split '( '#0009)
  ;  evalrpn = @{tks/tk ::
       ?{val.x :: [x;tks]
       ; val.op :: @.tks | @{[y;tks] ::
                           @@.tks | @{[x;tks] :: [x op y;tks]}}
       ++ x = tk reads["num] | @{[x;'()]::x}
       ;  op = [['+;+];['-;-];['*;*];['/;/]] assv tk}}
  ;  result = @{[r;[]] :: '() frm r; _ :: "error}}
  next ('() readf[])}
beyond val . '()

boykobbatgmaildotcom