5
1
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.
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 – 2012-10-16T00:18:20.447
Of course, *now* I notice that Peter did a Java implementation. ::sigh:: – dmckee --- ex-moderator kitten – 2012-10-16T00:20:46.653
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 – 2012-10-16T00:26:57.847
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 --- ex-moderator kitten – 2012-10-16T00:30:28.560
By the way, the part you were quoting was the original challenge posed to the first year student. I can see how that could be "misinterpreted". Please edit the post if you can think of a better formulation. I don't want to restrict it to C only. – ReyCharles – 2012-10-16T00:36:57.370
should I cheat, and use forth, where the answer would be
– SeanC – 2012-10-17T15:35:46.560.
(1 char): test:1 2 3 4 5 * * * * 2 +
<br>ok.
<br>.
<br>122 ok
That's using the forth interpreter. You have to make a program that given a string of integers,
+
and*
outputs the result. I tried the following:echo 1 2 + | gforth -e '.'
which (obviously) doesn't work. – ReyCharles – 2012-10-17T22:38:14.4971This 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 – 2012-10-18T17:54:52.830
In tcl if you have
– sergiol – 2017-05-23T23:11:18.823namespace path {::tcl::mathop}
, then you can do it directly without implementing anything: https://codegolf.stackexchange.com/a/106284/29325"first solution" is not a very nice winning criterion. Can't you make it a popularity contest? – John Dvorak – 2014-06-14T10:55:29.317
@JanDvorak yea, that may have been a better idea. At the time I thought this would be a difficult task. You're welcome to restate the task (if the rules allow it - you have my permission in any case). – ReyCharles – 2014-06-15T00:45:35.350
@ReyCharles Actually, now the second answer has 3 more votes than the first, so it should be declared winner – None – 2014-06-15T10:58:19.763