RPN calculator without pointers

Question

Me and some other students were at a bar discussing programming languages, in particular the C programming language. At some point a first year student said he didn't need no damn pointers. Another student said that he couldn't use arrays either since "they're basically pointers".

This led to a programming challenge:
Implement a reverse polish notation calculator in C without using arrays and pointers.

Description

You must implement a RPN calculator that

• operates on integers,
• supports addition (+),
• supports multiplication (*).

Your implementation

• must not use pointers or arrays
• you may use structs
• the input is read from stdin
• your lexer may use pointers and arrays (but it shouldn't be needed)
• when EOF is read then print the top of the stack
• the behavior can be as undefined as you want for malformed input
• should be in a language sufficiently c-like that the "no-pointers and no-arrays" restriction has a sensible interpretation (please elaborate if you think people may not get it)

The lexer could have a signature a la this^{Note: this is not taken from my own code. Please tell me if there's an error or it looks unreasonable}

typedef enum {
  val,
  op,
  eof
} TYPE;

typedef enum {
  add,
  mul
} OPERATION;

typedef struct {
  TYPE type;
  union {
    int val;
    OPERATION op;
  } dat;
} token;

token next();

A solution using a stack with push() and pop() could look something like this:

token t;
while ((t = next()).type != eof) {
  switch (t.type) {
    case val:
      push(t.dat.val);
    case op:
      switch (t.dat.op) {
        case add:
          int v1 = pop();
          int v2 = pop();
          push(v1+v2);
        case mult:
          int v1 = pop();
          int v2 = pop();
          push(v1*v2);
      }
    case eof:
      printf("Result: %d\n", pop());
  }
}

Other languages than C are also accepted, but the constraints should be comparable. It is hard to state the constraints in a way that fits all languages, but something like »all used data structures must have fixed size and fixed "depth"«. If there's any doubt please ask in the comments.

_{I have a solution that I can post. After cleaning up the code a bit. I wrote it the morning after while hungover.}

Answer 1

This is pretty ugly, but I think it works. I've avoided using null to make it as obvious as possible that the references could be passed on the stack. I may rewrite this in the morning to have an extra token type of NULL.

import java.io.IOException;

public class RPN
{
    public static void main(String[] args) throws IOException {
        Token result = depth0();
        if (result.type != Token.EOF) throw new IllegalStateException("Bad input");
        System.out.println(result.value);
    }

    private static Token depth0() throws IOException {
        Token tok = Lexer.lex();
        if (tok.type != Token.NUMBER) throw new IllegalStateException("Bad input");
        return depth1(tok);
    }

    private static Token depth1(Token s1) throws IOException {
        while (true) {
            Token s2 = Lexer.lex();
            switch (s2.type) {
                case Token.EOF:
                    return new Token(Token.EOF, s1.value);
                case Token.NUMBER:
                    s1 = depth2(s1, s2);
                    if (s1.type == Token.EOF) return s1;
                    break;
                default:
                    throw new IllegalStateException("Bad input");
            }
        }
    }

    private static Token depth2(Token s1, Token s2) throws IOException {
        while (true) {
            Token s3 = Lexer.lex();
            switch (s3.type) {
                case Token.EOF:
                    return new Token(Token.EOF, s2.value);
                case Token.OPERATOR:
                    return new Token(Token.NUMBER, s3.value == Token.OP_PLUS ? s1.value + s2.value : s1.value * s2.value);
                case Token.NUMBER:
                    s2 = depth2(s2, s3);
                    if (s2.type == Token.EOF) return s2;
                    break;
                default:
                    throw new IllegalArgumentException("Bug in lexer");
            }
        }
    }

    static class Lexer {
        private static boolean hasPushback = false;
        private static int pushback;

        private static int read() throws IOException {
            if (hasPushback) {
                hasPushback = false;
                return pushback;
            }

            // Assume input is in ASCII
            return System.in.read();
        }

        private static void pushback(int ch) {
            if (hasPushback) throw new IllegalStateException();
            hasPushback = true;
            pushback = ch;
        }

        public static Token lex() throws IOException {
            while (true) {
                int ch = read();
                switch (ch) {
                    case -1:
                        return new Token(Token.EOF, Token.EOF);
                    case '-':
                        return new Token(Token.NUMBER, -lexInteger(0));
                    case '0': case '1': case '2':
                    case '3': case '4': case '5':
                    case '6': case '7': case '8':
                    case '9':
                        return new Token(Token.NUMBER, lexInteger(ch - '0'));
                    case '+':
                        return new Token(Token.OPERATOR, Token.OP_PLUS);
                    case '*':
                        return new Token(Token.OPERATOR, Token.OP_TIMES);
                    default:
                        // Whitespace or comment
                        break;
                }
            }
        }

        private static int lexInteger(int value) throws IOException {
            while (true) {
                int ch = read();
                if (ch < '0' || ch > '9') {
                    pushback(ch);
                    return value;
                }

                value = value * 10 + (ch - '0');
            }
        }
    }

    static class Token {
        public static final int NUMBER = 0;
        public static final int OPERATOR = 1;
        public static final int EOF = -1;

        public static final int OP_PLUS = 0;
        public static final int OP_TIMES = 1;

        public final int type;
        public final int value;

        public Token(int type, int value) {
            this.type = type;
            this.value = value;
        }
    }
}

Sample usage:

$ javac RPN.java && java RPN <<<"1 2 3 4 5 ****2+"
122

Answer 2

This is a stand-alone C version, it doesnt require any external lexer. It works recursivly, like ratchet freaks solution.

All characters that are not +, *, - or numbers are treated as spaces. A - is treated as a space if it is not directly followed by a number.

#include <stdio.h>

int rpn(int n1, int n2) {
        int c, sign = 1, skip = 0;
        if(n1 < 0) sign = -1;
        do {
                c = getchar();
                if(c == '+') return n1+n2;
                if(c == '*') return n1*n2;
                if(c >= 48 && c <= 57) {
                        if(!skip) n1 = n1 * 10 + sign * (c - 48);
                        else n1 = rpn(sign * (c - 48), n1);
                } else {
                        skip = 1;
                        sign = 1;
                }
                if(c == '-') sign = -1;
        } while(c != EOF);
        return n1;
}

void main() {
        printf("%d\n", rpn(0, 0));
}

Answer 3

use recursion:

enum TYPE {
  val,
  op,
  eof
};

enum OPERATION {
  add,
  mul
};

struct token{
  TYPE type;
  union {
    int val;
    OPERATIOIN op;
  }
}

token parse(int val1,int val2){
    token t;
    //next() is the lexer
    while((t=next()).type!=TYPE.EOF){
        if(t.type==TYPE.op){//calculate the value
            return token(TYPE.val,t.op==add?val1+val2:val1*val2);
        }else if(t.type==TYPE.val){
            //recurse and pass the top 2 values on the stack
            t= parse(val2,t.val);
            if(t.type==TYPE.eof)return t;
            else val2=t.val;
        }else{
             return token(eof,val2);
        }
    }
}

I returned token so I can stop the recursion cleanly

Answer 4

2 uses of pointers are collected at the top, and are permitted by the rules as these are a necessary part of I/O at the level of file descriptors. Uses C99 compound literals and POSIX low-level file operations, reading and writing one byte at a time. There is also one implicit FILE * returned by tmpfile() which is immediately converted by fileno() to an integer.

This code implements the RPN calculator as a Semi-Thue system that works like a queue. ("Thue" is pronounced /too-ay/, like "2 A".) It uses iteration and a tempfile to evaluate the formula left-to-right, examining up to 3 tokens, possibly reducing, and writing into a new temp file for the next iteration.

It waits for enter before each pass. Terminate with an interrupt signal (ctrl-C). A simple extension would allow it to detect when a string is no longer reducing from one pass to the next, and terminate.

#define Read(f,x) read(f,&x,1)
#define Write(f,x) write(f,&x,1),write(1,&x,1)

#include <math.h>
#include <stdio.h>
#include <string.h>
#include <sys/types.h>
#include <unistd.h>

typedef union {
    enum tag {number, oper, eof} tag;
    struct {
        enum tag tag;
        int val;
    } num;
    struct {
        enum tag tag;
        char val;
    } op;
} token;

token input(int in){
    char b;
    int a;
    char o;
    a=0;
    o=0;
    do {
        if (!Read(in,b)) {
            return (token){.tag=eof};
        }
        if (b=='\n') {
            return (token){.tag=eof};
        }
        if (b>='0'&&b<='9') {
            a*=10;
            a+=b-'0';
        } else if (b=='+'||b=='*') {
            o=b;
        }
    } while(b!=32);

    if (o)
        return (token){.op.tag=oper, .op.val=o};
    else
        return (token){.num.tag=number, .num.val=a};
}

output(int out, token t){
    char b;
    int c;
    switch(t.tag){
    case number:
        c=t.num.val>9?(int)floor(log10((double)t.num.val)):0;
        //b = c + '0'; Write(out,b);
        for( ; c>=0; c--) {
            b = '0' + (t.num.val/(int)pow(10.0, c)) % 10;
            Write(out,b);
        }
        break;
    case oper:
        b = t.op.val;
        Write(out,b);
        break;
    case eof:
        b = '\n';
        Write(out,b);
        return;
    }
    b = 32;
    Write(out,b);
}

int rpn(int in, int out) {
    token x,y,z;
    char b;
read_x:
    //b='X';write(1,&b,1);
    x = input(in);
    //b='A'+x.tag;write(1,&b,1);
    switch (x.tag){
    case eof:
        output(out, x);
        return EOF;
    case oper:
        output(out, x);
        goto read_x;
    }
read_y:
    //b='Y';write(1,&b,1);
    y = input(in);
    //b='A'+y.tag;write(1,&b,1);
    switch (y.tag){
    case eof:
        output(out, x);
        output(out, y);
        return EOF;
    case oper:
        output(out, x);
        output(out, y);
        goto read_x;
    }
read_z:
    //b='Z';write(1,&b,1);
    z = input(in);
    //b='A'+z.tag;write(1,&b,1);
    switch(z.tag){
    case eof:
        output(out, x);
        output(out, y);
        output(out, z);
        return EOF;
    case number:
        output(out, x);
        x.num.val = y.num.val;
        y.num.val = z.num.val;
        goto read_z;
    case oper:
        switch(z.op.val){
        case '+':
            x.num.val = x.num.val + y.num.val;
            break;
        case '*':
            x.num.val = x.num.val * y.num.val;
            break;
        }
        output(out, x);
        goto read_x;
    }
    return 0;
}

main(){
    int i=0,o;
    char b;
    token t;
    do {
        o = fileno(tmpfile());
        rpn(i,o);
        i = o;
        lseek(i, 0, SEEK_SET);
    } while(Read(0,b));
}

In action:

./2A
1 2 3 4 5 6 7 8 9 10 + + + + + + + + + 
1 2 3 4 5 6 7 8 19 + + + + + + + + 

1 2 3 4 5 6 7 27 + + + + + + + 

1 2 3 4 5 6 34 + + + + + + 

1 2 3 4 5 40 + + + + + 

1 2 3 4 45 + + + + 

1 2 3 49 + + + 

1 2 52 + + 

1 54 + 

55 

55 

55 

Answer 5

Befunge 98 - 46 bytes

v       >\3p
>2+:~:a-|
 v      >n
v>
>.@

The "no pointers or arrays" restriction only barely makes sense in befunge. Individual stacks on the stack stack could be interpreted to mean an array, but this program doesn't use the stack stack. The only data type this program uses are numbers.

This program adds .@ (which prints out the top of the stack, then ends the program) to the end of your input and interprets it as befunge code.

Answer 6

RProgN, 2 Bytes

do

Evaluates as RProgN. Any valid RPN is valid Syntax is RProgN by design, And RProgN is stack based. However, this prints the entire stack after running, not just the top of the stack. This can be resolved with:

do p w{ }

Which prints the top of the stack, then empties the stack.

Try it online