Take the 2-minute tour ×
Programming Puzzles & Code Golf Stack Exchange is a question and answer site for programming puzzle enthusiasts and code golfers. It's 100% free, no registration required.

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 thisNote: 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.

share|improve this question
    
I don't see [language-agnostic] as compatible with a language tag such as [c] so I stripped one one them in keeping with the text "Implement a reverse polish notation calculator in C without using arrays and pointers." –  dmckee Oct 16 '12 at 0:18
    
Of course, now I notice that Peter did a Java implementation. ::sigh:: –  dmckee Oct 16 '12 at 0:20
    
I see what you mean. The reason I put the C tag was because the problem is primarily defined in terms of C concepts. However, I will accept solutions in other languages (such as java) that satisfy "comparable" constraints, hence the [language-agnostic] tag. It is a bit difficult, I think, to define the constraints in a completely language agnostic way. I am therefore not sure if the [language-agnostic] tag applies here. I don't think [c] and [language-agnostic] are incompatible as such, though. Also, I can't sleep :-/ –  ReyCharles Oct 16 '12 at 0:26
    
I think "c-like langauges" would be a good phrase and then [language-agnostic] is reasonable. Heck, you could even leave the [c]. And then it would be clear that Peter was playing fair. Is that in keeping with your intent? –  dmckee Oct 16 '12 at 0:30
1  
This is an intriguing puzzle. I may try it when I get home. As an aside, that first year student is so naïve in thinking he will get away with not learning pointers. :) –  Ben Richards Oct 18 '12 at 17:54

4 Answers 4

up vote 4 down vote accepted

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
share|improve this answer
    
Looks good! It's a bit more clever than my own solution :-) I will review it again tomorrow, it's a bit late here. –  ReyCharles Oct 15 '12 at 23:05
    
Congratulations! You win. I hope you found the puzzle fun. –  ReyCharles Oct 16 '12 at 8:32

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));
}
share|improve this answer
    
That's pretty cool! I never thought "inlining" the lexer would make it so much shorter. –  ReyCharles Oct 18 '12 at 10:50

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

share|improve this answer
    
I don't think this quite works. You're missing the return statement in case of reading an EOF, and you need to handle the bootstrapping cases when you don't have two items on the stack. –  Peter Taylor Oct 16 '12 at 7:03
    
First of all, what language is this? Secondly, how would you run this? Also, what Peter Taylor said. –  ReyCharles Oct 17 '12 at 22:40
    
it's D it's run with parse(0,0) (completely valid ;P ) and I forgot to handle the eof case... –  ratchet freak Oct 17 '12 at 22:56

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 
share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.