# $Revision: 10482 $
# $Author: saulius $
# $Date: 2023-02-14 06:42:25 +0000 (Tue, 14 Feb 2023) $

Complex number Reverse Polish Notation calculator
=================================================
             Saulius Gražulis
              Vilnius, 2023

CONVENTIONS
===========

The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
"SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this
document are to be interpreted as described in RFC 2119 [1].

PROGRAM
=======

Write a Perl or Ada program that reads in complex numbers [5,6] and
operation specifications on them in Reverse Polish Notation order [2],
performs all operations specified in the input stream and writes the
result to STDOUT.

For this assignment, it is *not* allowed to use any external
libraries; arithmetic operations must be implemented using the
standard programming language means.

The program MUST be able to work in the currently supported Debian or
compatible and Ubuntu or compatible OSes.

Program name:
calc-complex

Program invocation:
calc-complex input.dat
calc-complex < input.dat
calc-complex input.dat > result.dat

PROGRAM FUNCTION
================

The program MUST read its input stream (from a file or STDIN), skip
comments and empty lines, and process all input data. Input data
elements MAY be either:

a) complex numbers, specified as their real and imaginary parts in
   real number syntax; or

b) operation codes, specified as operation symbols (e.g. '+', '-'
   (without the quotes)), or function names (e.g. 'sqrt', 'sin'
   (without the quotes)).

When a number is encountered in the input stream, it is supposed to be
pushed onto stack. The program MAY limit the maximum depth of the
stack; if this is the case, the maximum permitted stack depth MUST be
at least 64 numbers.

When an operation is encountered in the input stream, the number of
operands necessary for performing this operation is supposed to be
popped from the stack, the operation performed in the processed number
arithmetic, and the result should be pushed back onto the stack.

At the end of the data stream (all input files and/or STDOUT) the top
of the stack MUST be printed to STDOUT in the same syntax in which it
is read in.

Supported operations
--------------------

The program MUST support the following operations:

binary:

-- addition:       +
-- subtraction:    -
-- multiplication: *
-- division:       /

unary:

-- negation: neg
-- complex conjugation: conj
-- absolute value: abs
-- square root: sqrt

The square root MUST push onto the stack *two* values of the complex
square root.

stack maintenance:

-- remove the top stack element: drop
-- duplicate the top stack element: dup
-- exchange the two top stack elements: swap
-- rotate the top N elements of the stack: rot N

The positive rotation number N (e.g. 3) moves the top element to the
position 3 (1-based) on the stack, and at the same time moves all
elements from depth N to depth 2 one stack position *up* (towards the
top of the stack; i.e. the 2-nd element from the top becomes the
topmost).

The negative rotation number (e.g. -3) rotates the stack in the
opposite direction.

Examples
--------

Example 1:

Stack:

x <- Top of the stack (TOS)
y
z
t

'rot 3' yields:

y <- TOS
z
x
t

'rot -3' yields:

z <- TOS
x
y
t

Example 2:

'rot 1' and 'rot -1' are equivalent to 'swap'.

Real number syntax
------------------

Real numbers processed and output by the program MUST conform to the
usual real number syntax of programming languages, i.e. it MUST
match the following Extended Regular Expression (ERE) or Perl
Compatible Regular Expression:

-- ERE: [-+]?([0-9]+(\.[0-9]\*)?|\.[0-9]+)([eE][-+]?[0-9]+)?
-- PCRE:[-+]?(?:\d+(\.\d*)?|\.\d+)(?:[eE][-+]?\d+)?

Efficiency considerations
-------------------------

The program MAY *not* "slurp" the whole file into RAM; only the values
currently placed onto the stack SHOULD be kept in RAM.

INPUTS AND OUTPUTS
==================

The program MUST read all files provided on the command line and
process them. If a file name is a lone hyphen ('-'), the program MUST
read from STDIN when processing this file name (to specify the file
that has a name consisting of the lone hyphen, prepend it with the
current directory name, i.e. "./-").

The program SHOULD NOT assume that STDIN or any other file is
rewindable.

If the files are not provided, the program MUST read from STDIN.

The program MUST write its results to STDOUT.

INPUT
=====

Program input consists of text lines with the following permissible
items:

- Comments. Lines that start with the '#' (hash, ASCII code 35)
  character on the first line MUST be treated as comments and ignored;

- Empty lines (i.e. lines containing no characters or only white space
  characters – space or TAB characters) MUST be ignored;

- Lines containing 2 real numbers; these numbers MUST be treated as
  the real (the first number) and imaginary (the second number) part
  of the complex number on this line. Essentially the programs reads
  numbers in the (hyper)complex number format [3], adapted for complex
  numbers.

- lines, containing operation codes ('+', '-', 'sqrt', ...), as
  described in the "Supported operations" subsection.

A comment line of the file MAY contain the the column definitions. The
column definition comment MUST start with the '#@ ' character
sequence. It the SHOULD contain white space-separated tokens '1' and
'i', indicating real and imaginary unit columns. White space MAY
follow these tokens till the end of the line. No other tokens are
permitted on this line.

When multiple copies of the column line are encountered, they MUST be
the same. If the column definition comment is encountered, the program
MUST check whether the column definition lines conforms the
above-mentioned specification and that the columns are in the order
that the program can process.

Example:
--------

#-----------8<----------------------
# Input operation stream
#@ 1     i
 1.2   3.1
 0.0   1.12

+
sqrt
*

# Empty lines above MUST be ignored.
#----------->8----------------------

OUTPUT
======

Data must be output to standard output in the same format as data in
input files (format described in [3]), indicating one complex number
of the result. The first line MUST be a comment listing the SVN of the
program used (or other version control systems) Id, for example:

# Id: program_name 1 2011-09-28 07: 41: 19Z author

Note that there should be no dollar symbols ('$') around the Id:
string, unlike in the SVN keywords (but SVN keywords SHOULD be used to
generate the string!)

The second line MUST be the column type designator line:

	#@ 1 i

After that, the result of all arithmetic operations must be printed as
a single complex number in the vector format.

Example:
--------

# Id: program_name 1 2011-09-28 07:41:19Z author
#@ 1 i
0.125 -0.125

OPTIONS
=======

For this assignment, the program does not need to support any options.

ERROR DIAGNOSTICS
=================

All error messages MUST be output to STDERR. If an error is detected,
a suitable non-zero status (exit) code MUST be returned.

The program MUST detect abnormal situation and report them. An
informative user-friendly error reporting should be used. IN
particular, the error message MUST contain: the program name, the
input file name where the error was detected (use '-' without the
quotes as a file name if your input is STDIN), input line number where
the error was detected; quoted example of the erroneous input. The
program MAY output error position in the first character where the
error was detected. The error messages should be informative and
permit user to fix the error.

Perl functions 'die' and 'warn', invoked with and without the "\n"
character at the end of the message are examples of acceptable error
reporting. The native Perl diagnostics (switched on by "use warnings")
and file conditions detected by "while(<>) {...}" construct SHOULD be
used for error reporting.

The program SHOULD attempt to recover from errors and SHOULD continue
its operation as long as possible.

The program must support at least two error severity levels, ERROR and
WARNING. The program MAY support the third error level; if supported
it should be called NOTE. Error severity level ("ERROR", "WARNING" or
"NOTE") SHOULD be selected based on the validity of the program
output. The project MUST mandate the "ERROR" severity level for all
conditions that do not allow to compute the correct and correctly
formatted result.

The "WARNING" error level SHOULD be mandated for those conditions when
the output is physically, logically and syntactically correct but
might be unusual or not expected by the user (e.g. empty or degenerate
output when such output is permitted by the task and the output
format).

The "NOTE" level SHOULD be mandated for by conditions that do not
interfere withe the generation of correct and expected results, but
might be of interest for the user when interpreting the output data.

The following conditions MUST be detected and reported:

-- missing, unreadable, unreachable files;

-- system read errors;

-- wrong column description;

-- wrong input number format;

-- number of input number components is not 2

-- not enough values on the stack to perform the requested operation
   (e.g. less than 2 values for '+' or '*'; less than N values for
   'rot N'; ERROR);

-- not enough values on the stack for printing at the end of the
   program, i.e. empty stack (ERROR);

-- extra values on the stack (i.e. more than one value) at the end of
   the program (WARNING);

If the program detects wrong format of at least one input number which
participates in arithmetic, the output result MUST be the "NaN"
string (IEEE 754 Not-a-Number) [4];

If the program encounters floating point overflow condition while
processing a matrix, its output on that line MUST be "Inf" (IEEE 754
Infinity) with a relevant sign on the corresponding output line.

Error message content
---------------------

Error messages SHOULD contain at least:

-- the name of the program that diagnosed the error;

-- the name of the file that was being processed when the error
   happened (if appropriate); use the "-" string (with quotation
   marks) or the name "STDIN" (without the quotes) if STDIN was being
   processed when the error happened;

-- the line of the file and the character position within the line
   (the column) where the error was detected (if appropriate);

-- a short (20–40 characters) citation of the context where the error
   happened (if appropriate);

-- a short but informative message indicating the cause of the error
   and possible actions to rectify situation. Exclamatory marks SHOULD
   NOT be used in the messages.

Example:
--------

EXIT STATUS
===========

The program MUST return the 0 exit status if all computations were
performed correctly, 1 if some results were NaNs, 2 if there were
WARNING level issues reported, and 3 if a fatal errors (of the level
ERROR) occurred.

QUESTIONS TO THINK ABOUT
========================

Are there numbers that are non-zero but give zero product when
multiplied together? (i.e. are there zero divisors?)

Is the multiplication commutative?

Is the multiplication associative?

What subset of numbers has multiplicative inverses?

In what practical applications are these numbers used? In STEM? In
Bioinformatics? What other number systems could be useful for
Bioinformatics?

References
==========

1. S. Bradner "Key words for use in RFCs to Indicate Requirement
   Levels", RFC 2119, URI: https://tools.ietf.org/html/rfc2119

2. Wikipedia. Reverse Polish notation (2023) URL:
   https://en.wikipedia.org/wiki/Reverse_Polish_notation [accessed
   2023-02-07T11:19+02:00; permalink:
   https://en.wikipedia.org/w/index.php?title=Reverse_Polish_notation&oldid=1137037456]

3. Saulius Gražulis (2020) Hiperkompleksinių skaičių vektorinis
   formatas.
   https://saulius.grazulis.lt/~saulius/paskaitos/VU/bioinformatika-III/užduotys-praktikai/1-užduotis/formatai/hiperkompleksinių-skaičių-vektorinis-formatas.txt
   [last accessed: 2023-02-07T12:14+02:00]

4. Wikipedia. IEEE 754 (2023) URL: https://en.wikipedia.org/wiki/IEEE_754
   [accessed 2023-02-13T15:27+02:00; permalink:
   https://en.wikipedia.org/w/index.php?title=IEEE_754&oldid=1135219367] 

5. Wikipedia. Complex number (2023) URL:
   https://en.wikipedia.org/wiki/Complex_number [accessed
   2023-02-13T14:16+02:00; permalink:
   https://en.wikipedia.org/w/index.php?title=Complex_number&oldid=1137555564]

6. H.-B. Ebbinghaus et al. (1995) Numbers. Springer, ISBN:
   3-540-97497-0 (ISBN URL: https://isbnsearch.org/isbn/3540974970)

Colophon
========

$Id: 01-complex-numbers-RPN-calculator.txt 10482 2023-02-14 06:42:25Z saulius $
$URL: file:///home/saulius/svn-repositories/paskaitos/VU/bioinformatika-III/u%C5%BEduotys-praktikai/skai%C4%8Di%C5%B3-u%C5%BEduotis-RNP-calculator/en/01-complex-numbers-RPN-calculator.txt $