RPN calculator without pointers [closed]

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.}

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 --- ex-moderator kitten
– dmckee --- ex-moderator kitten, Commented Oct 16, 2012 at 0:18
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
– Ben Richards, Commented Oct 18, 2012 at 17:54
"first solution" is not a very nice winning criterion. Can't you make it a popularity contest? — John Dvorak
– John Dvorak, Commented Jun 14, 2014 at 10:55
In tcl if you have namespace path {::tcl::mathop}, then you can do it directly without implementing anything: codegolf.stackexchange.com/a/106284/29325 — sergiol
– sergiol, Commented May 23, 2017 at 23:11
I’m voting to close this question because not using pointers or arrays, and having a "lexer", is a completely unobservable requirement. This question would not be acceptable if posted today. — emanresu A
– emanresu A, Commented May 15, 2022 at 23:02

Community · Accepted Answer · 2017-04-13 12:39:07Z

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)); }

That's pretty cool! I never thought "inlining" the lexer would make it so much shorter. — ReyCharles
– ReyCharles, Commented Oct 18, 2012 at 10:50

Peter Taylor · Accepted Answer · 2012-10-15 22:38:38Z

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

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
– ReyCharles, Commented Oct 15, 2012 at 23:05

ratchet freak · Accepted Answer · 2012-10-17 22:56:58Z

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

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
– Peter Taylor, Commented Oct 16, 2012 at 7:03
First of all, what language is this? Secondly, how would you run this? Also, what Peter Taylor said. — ReyCharles
– ReyCharles, Commented Oct 17, 2012 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
– ratchet freak, Commented Oct 17, 2012 at 22:56

luser droog · Accepted Answer · 2014-06-14 09:17:30Z

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

Community · Accepted Answer · 2020-06-17 09:04:33Z

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

Stack Exchange Network

RPN calculator without pointers [closed]

Description

5 Answers 5

RProgN, 2 Bytes

Linked

Hot Network Questions

RPN calculator without pointers [closed]

Description

5 Answers 5

RProgN, 2 Bytes

Linked

Related

Hot Network Questions