# Beginner Programming Challenge #11

Show 75 post(s) from this thread on one page
Page 1 of 10 123 ... Last
• March 29th, 2010
schauerlich
Beginner Programming Challenge #11
Beginner Programming Challenge #11

This challenge is closed. You're welcome to submit an entry and ask for feedback, but the winner has already been selected.

Welcome to the 11th Beginner Programming Challenge! Although I did not win the 10th programming challenge, Bachstelze has graciously allowed me to host this one.

If you need help, feel free to drop by on IRC on irc.freenode.net in #ubuntu-beginners-dev.

Let's get started.

Implement a Reverse Polish Notation (RPN) calculator.

What is RPN?
You're probably used to calculators using infix notation. With infix notation, you place an operator between two operands, and press enter to see the result. An example of infix notation:
Code:

`3 + 4`
Infix notation works well for basic expressions, but it is difficult to write complicated expressions without parentheses.

RPN, on the other hand, places operators after their operands. For example:
Code:

`3 4 +`
While this may seem odd at first, it has several convenient properties:
• It is possible to write arbitrarily long expressions in RPN which are unambiguous, and do not require parentheses.
• There is no need for an operator precedence hierarchy
• It is relatively easy for a computer to parse
• Calculations can be done as soon as an operator is specified - you do not need to consider the entire expression before beginning to evaluate it.

Here are a few more examples of RPN, with their infix notation counterparts
Code:

```3 4 - 5 + (3 - 4) + 5 3 4 5 * - 3 - (4 * 5) 5 1 2 + 4 * + 3 − 5 + ((1 + 2) * 4) − 3```
Requirements:
• Your program must be able to evaluate any valid RPN expression of reasonable length (~20 tokens) with the following operators: + - * / % ^ (division is true division. 10 3 / = 3.33)
• If the entered expression's syntax is invalid, your program should handle it gracefully (no segfaults or uncaught exceptions)
• Your program must handle divide by zero errors gracefully

Extra Credit:
• If interactive, allow users to quit without resorting to ^C.
• Plan for the future: make your code flexible so that it can be incorporated into other projects you may work on easily.
• Add more operators: anything that makes sense
• Gracefully handle all user input, from random characters to just a newline.

Extra Extra Credit:
• Add support for an infix notation mode by converting the expression to RPN and evaluating it with your RPN code.

Example output, for testing:
Code:

```eric@river:~\$ ./rpn > 3 4 + 7.0 > 10 3 / 3.33333333333 > 2 5 ^ 32.0 >  10 2 % 0.0 > 24 12 3 + 4 % / 6 - 4 * 3 ^ 512.0 > 10 2 2 % / Divided by Zero // Incorrect inputs: > 10 + 10 Not enough operands > 10 10 10 + Too many operands > > aw4ojghsiu5esrgs56u7ikdyjdt drthisu 5 hrtgh 5 5 + Unrecognized token > 45 6 + / & 4 Unrecognized token > q eric@river:~\$```
Caveats:
The wikipedia page has a good explanation of the algorithm for evaluating RPN, as well as a sample implementation in Python. Please try to think for yourself and only reference these if you're stuck. Submissions which are suspiciously similar probably won't win, and more importantly, you won't learn anything.

As always:
Any overly obfuscated code will be immediately disqualified without account for programmers skill. Please remember that these challenges are for beginners and therefore the code should be easily readable and well commented.

Any non-beginner entries will not be judged. Please use common sense when posting code examples. Please do not give beginners a copy paste solution before they have had a chance to try this for themselves.

And with that...
Have fun!
• March 29th, 2010
tooatw
Re: Beginner Programming Challenge #11
hi, i am new to this forum and i would like to enter this challange, do i just write here when i'm done or something? are all programming languages accepted?
• March 29th, 2010
s.fox
Re: Beginner Programming Challenge #11
Quote:

Originally Posted by tooatw
hi, i am new to this forum and i would like to enter this challange, do i just write here when i'm done or something? are all programming languages accepted?

Hello,

Provided you are a beginner then yes you can enter before the winner is announced. To enter simply post your solution here. Any language is allowed.

-Silver Fox
• March 29th, 2010
tooatw
Re: Beginner Programming Challenge #11
i'm almost done, it works fine for the first line, but if i enter the exact same thing on the second one, it doesnt work

alexander@amd64:~/1\$ ./1
>24 12 3 + 4 % / 6 - 4 * 3 ^
512.0
>24 12 3 + 4 % / 6 - 4 * 3 ^
3.0
• March 29th, 2010
schauerlich
Re: Beginner Programming Challenge #11
Quote:

Originally Posted by tooatw
i'm almost done, it works fine for the first line, but if i enter the exact same thing on the second one, it doesnt work

Without seeing your code, I'm guessing you don't reset your variables between runs.
• March 29th, 2010
tooatw
Re: Beginner Programming Challenge #11
i thought it was the variables, however i only reset the counter to the arrays, i didn't reset all the elements in the array because i thought it didn't matter since it will just overwrite them anyway

here's a screenshot of it in action, i think it pretty much resembles with your post

p.s. i know it could be done faster / better but i'm a beginner and i think thats what this topic is about anyway
• March 29th, 2010
lavinog
Re: Beginner Programming Challenge #11
Code:

`for (i=0;i<99;++i) num[i]=zero=k[i]=0;`
Are you setting zero to 0 99 times?
• March 29th, 2010
tooatw
Re: Beginner Programming Challenge #11
Quote:

Originally Posted by lavinog
Code:

`for (i=0;i<99;++i) num[i]=zero=k[i]=0;`
Are you setting zero to 0 99 times?

yes, i meant to put it to the other line actually, my mistake
• March 29th, 2010
tooatw
Re: Beginner Programming Challenge #11
Code:

```//Alexander Constantin Bledea - Beginner Programming Challenge #11 #include <stdio.h> //standard for i/o #include <stdlib.h> // standard again #include <string.h> // string library #include <math.h> // for the power function int i,true=2,k[99],is,is2,w,iv,si,dubios,nc,number,zero,neo,num[99]; /*  i is standard  true is something that is always true since i don't know the c version of "while true"  is is the empty spaces in the string counter  is2 is the 'how much till the end' counter  w is like a secondary i  si counts how many words are between two spaces since operators can only use one space  dubios seeks dubious behaviour  nc is the number counter  number is the temporary number  zero alerts if someone wants to divide by 0  neo is the not enough operators counter  num is the number array  */ char x[100]; //the string float n_to_f; // for the dubious output int main(){         while (true){                 for (i=0;i<99;++i) num[i]=k[i]=0; // reset the arrays                 i=is=is2=w=iv=si=dubios=nc=zero=neo=number=0; // reset the variables                 printf("> ");                 gets(x);                 if (strcmp(x,"exit")== 0) break;                 for (i=0;i<strlen(x);++i){ //find empty spaces and keep track of them in k                         if (x[i]==' ') {                                         k[is] = i;                                         ++is;                         }                 }                 if (k[is] != strlen(x)) {k[is]=strlen(x);++is;} // add to the counter the last element                 iv=0;// needed later on                 for (w=0;w<is;++w){  // for all the empty spaces                         is2=k[w]-iv; //how many characters does the string fragment have                         number=0; //reset the number                         for (i=iv;i<k[w];++i){ //figure out what the number is                                 si=is2;                                 switch(x[i]){                                         case '0'...'9': number += ((x[i] - '0') * pow( 10.0 , is2-1));                                                                         --is2 ;                                                                         if (is2==0) { //when is reaches 0 save the number                                                                                 num[nc]=number;                                                                                 ++nc;                                                                         }                                                                         break;                                                case  '+': if (si==1){ if(nc>1){ num[nc-2]=num[nc-2]+num[nc-1]; num[nc-1]=num[nc];--nc;} else ++neo;} else ++dubios;break;                                         case  '-': if (si==1){ if(nc>1){ num[nc-2]=num[nc-2]-num[nc-1]; num[nc-1]=num[nc];--nc;} else ++neo;} else ++dubios;break;                                         case  '/': if (si==1){ if(nc>1){ if (num[nc-1]!=0){ num[nc-2]=num[nc-2]/num[nc-1]; num[nc-1]=num[nc]; --nc;} else ++zero;}  else ++neo;} else ++dubios;break;                                         case  '*': if (si==1){ if(nc>1){ num[nc-2]=num[nc-2]*num[nc-1]; num[nc-1]=num[nc]; --nc;} else ++neo;} else ++dubios;break;                                         case  '^': if (si==1){ if(nc>1){ num[nc-2]=pow(num[nc-2],num[nc-1]); num[nc-1]=num[nc]; --nc;} else ++neo;} else ++dubios;break;                                         case  '%': if (si==1){ if(nc>1){ num[nc-2]=num[nc-2]%num[nc-1]; num[nc-1]=num[nc]; --nc;} else ++neo;} else ++dubios;break;                                                                                 //for all cases of operands if the string fragment is wider than 1 caracter mark it as dubious behavior and if you dont have at least 2 operands mark it down                                         default: ++dubios;break;                                         //anything else goes to dubious behaviour                                 }                                                 }                         iv=k[w];//we need this to find out the word size                         ++iv;                 }         n_to_f=num[nc-1];//transform it to float because thats what the post asks for     if (dubios==0){//if nothing is dubious ... this should be obvious                 if (zero!=0) printf("Divided by Zero\n");                 else if (neo>0) printf("Not enough operands\n");                 else if (neo==0 &&nc>1) printf("Too many operands\n");                 else if (nc==0); //if empty string                 else printf("%.1f\n",n_to_f); }// if everything goes to plan print the number     else printf("Unrecognized token\n");     } return 0; }```
• March 29th, 2010
Compyx
Re: Beginner Programming Challenge #11
I would suggest breaking the code up into functions, adding some whitespace here and there and indenting properly. That would make the code easier to read, debug and extend.

The C idiom for `while (true)' is `while (1)' or (less common and less readable) `for ( ; ; )'.

You can define true if you want:
Code:

```#define true 1 #define false 0```
or:
Code:

`typedef enum { false, true } bool;`
will give you a boolean type should you need it.
Show 75 post(s) from this thread on one page
Page 1 of 10 123 ... Last