Page 1 of 3 123 LastLast
Results 1 to 10 of 91

Thread: Beginner Programming Challenge #11

Hybrid View

  1. #1
    Join Date
    Apr 2007
    Location
    NorCal
    Beans
    1,149
    Distro
    Ubuntu 10.04 Lucid Lynx

    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.

    Task:

    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.

    Please provide instructions for how to run your program along with your submission.

    And with that...
    Have fun!
    Last edited by schauerlich; April 18th, 2010 at 08:11 AM.
    Posting code? Use the [code] or [php] tags.
    I don't care, I'm still free. You can't take the sky from me.

  2. #2
    Join Date
    Mar 2010
    Beans
    31
    Distro
    Ubuntu 9.10 Karmic Koala

    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?

  3. #3

    Re: Beginner Programming Challenge #11

    Quote Originally Posted by tooatw View Post
    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

  4. #4
    Join Date
    Mar 2010
    Beans
    31
    Distro
    Ubuntu 9.10 Karmic Koala

    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

  5. #5
    Join Date
    Apr 2007
    Location
    NorCal
    Beans
    1,149
    Distro
    Ubuntu 10.04 Lucid Lynx

    Re: Beginner Programming Challenge #11

    Quote Originally Posted by tooatw View Post
    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.
    Posting code? Use the [code] or [php] tags.
    I don't care, I'm still free. You can't take the sky from me.

  6. #6
    Join Date
    Mar 2010
    Beans
    31
    Distro
    Ubuntu 9.10 Karmic Koala

    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
    Attached Images Attached Images
    Last edited by tooatw; March 29th, 2010 at 04:25 PM.

  7. #7
    Join Date
    Mar 2010
    Beans
    31
    Distro
    Ubuntu 9.10 Karmic Koala

    Re: Beginner Programming Challenge #11

    Quote Originally Posted by schauerlich View Post
    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:~$
    i see that you modified it
    so tell us exactly what happens
    if the result is an integer only display one digit after the dot (why?) otherwise display 10?
    why cant it be standard one digit after the , or standard 10

  8. #8
    Join Date
    Apr 2007
    Location
    NorCal
    Beans
    1,149
    Distro
    Ubuntu 10.04 Lucid Lynx

    Re: Beginner Programming Challenge #11

    Quote Originally Posted by tooatw View Post
    i see that you modified it
    so tell us exactly what happens
    if the result is an integer only display one digit after the dot (why?) otherwise display 10?
    why cant it be standard one digit after the , or standard 10
    Yes I did modify it, sorry. I wanted to clarify that division should be true division - that means 10 3 / should be 3.333..., not 3.0. You should cast to a float before you do the division, not after.
    Posting code? Use the [code] or [php] tags.
    I don't care, I'm still free. You can't take the sky from me.

  9. #9
    Join Date
    Jun 2009
    Beans
    1,043

    Re: Beginner Programming Challenge #11

    Just a quick fyi that would help all of us studying code posted here- edit your text editor's config files to enter spaces instead of tab characters when the tab key is pressed. For example- in my .vimrc I have these lines-
    Code:
    set smartindent
    set tabstop=4
    set shiftwidth=4
    set expandtab
    I don't recall exactly what each line does- I copied it off of some website with VIM information. All that matters is that when I press the tab key - I get four spaces instead of a tab character.

    I copied and pasted the above code into vim, and I've got a huge mess to clean up before I can run or study it.

    BM

    edit- nevermind- I think I figured out what my problem was...
    Last edited by blur xc; March 29th, 2010 at 10:21 PM.

  10. #10
    Join Date
    Feb 2006
    Beans
    68
    Distro
    Ubuntu 10.04 Lucid Lynx

    Re: Beginner Programming Challenge #11

    my messy c++ code that works for rpn:

    Code:
    #include <iostream>
    #include <fstream>
    #include <string>
    #include <vector>
    #include <cstdlib>
    #include <cmath>
    #include <iomanip>
    
    using namespace std;
    
    void rpn(const vector<string>& in)
    {
    	string out, temp;
    	double answer = 0;
    	double arguments[20] = {0};
    	int arg_count = 0;
    	unsigned int index = 0;
    	bool error = false;
    	
    	do{
    		temp = in[index];
    		int int_temp = atoi(temp.c_str());	//used to check if word is a number
    		char char_temp = temp[0];		//used to check if word is an operator
    				
    		if(int_temp > 0) 			//word is a non-zero number
    		{
    			arguments[arg_count] = int_temp;
    			arg_count ++;
    		}
    		else if(char_temp == 48) 		//word is zero
    		{
    			arguments[arg_count] = 0;
    			arg_count ++;
    		}
    		else if(index <= 1)		//encountered an operator/gibberish before having 2 arguments
    		{
    			error = true;
    			index = in.size();
    			cout << "Error in input." << endl;
    		}
    		else if(char_temp == 43) 		// + operator
    		{
    			if(arg_count > 1)
    			{
    				answer = arguments[arg_count-2] + arguments[arg_count-1];
    				arguments[arg_count-2] = answer;
    				arg_count--;
    			}
    			else if(arg_count <= 1)
    			{
    				answer += arguments[arg_count-1];
    				arg_count--;
    			}
    		}
    		else if(char_temp == 37) 		// % operator
    		{
    			if(arg_count > 1)
    			{
    				answer = static_cast<int>(arguments[arg_count-2]) % static_cast<int>(arguments[arg_count-1]);
    				arguments[arg_count-2] = answer;
    				arg_count--;
    			}
    			else if(arg_count <= 1)
    			{
    				answer = static_cast<int>(arguments[arg_count-1]) % static_cast<int>(answer);
    				arg_count--;
    			}
    			 
    		}
    		else if(char_temp == 42)		 // * operator
    		{
    			if(arg_count > 1)
    			{
    				answer = arguments[arg_count-2] * arguments[arg_count-1];
    				arguments[arg_count-2] = answer;
    				arg_count--;
    			}
    			else if(arg_count <= 1)
    			{
    				answer *= arguments[arg_count-1];
    				arg_count--;
    			}
    		}
    		else if(char_temp == 45) 		// - operator
    		{
    			if(arg_count > 1)
    			{
    				answer = arguments[arg_count-2] - arguments[arg_count-1];
    				arguments[arg_count-2] = answer;
    				arg_count--;
    			}
    			else if(arg_count <= 1)
    			{
    				answer -= arguments[arg_count-1];
    				arg_count--;
    			}
    		}
    		else if(char_temp == 47) 		// / operator
    		{
    			if(arg_count > 1)
    			{
    				if(arguments[arg_count-1] == 0)
    				{
    					cout << "Dividing by zero!" << endl;
    					error = true;
    			 		index = in.size();
    				}
    				else
    				{
    					answer = arguments[arg_count-2] / arguments[arg_count-1];
    					arguments[arg_count-2] = answer;
    					arg_count--;
    				}
    			}
    			else if(arg_count <= 1)
    			{
    				if(arguments[arg_count-1] == 0)
    				{
    					cout << "Dividing by zero!" << endl;
    					error = true;
    			 		index = in.size();
    				}
    				else
    				{
    					answer /= arguments[arg_count-1];
    					arg_count--;
    				}
    			}
    		}
    		else if(char_temp == 94) 		// ^ operator
    		{
    			if(arg_count > 1)
    			{
    				answer = pow(arguments[arg_count-2], arguments[arg_count-1]);
    				arguments[arg_count-2] = answer;
    				arg_count--;
    			}
    			else if(arg_count <= 1)
    			{
    				answer = pow(arguments[arg_count-1], answer);
    				arg_count--;
    			}
    		}
    		else
    		{
    			cout << "Unrecognized token." << endl;
    			error = true;
    			index = in.size();
    		}
    		
    		index++;
    
    	}while(index < in.size());
    	
    	if(arg_count == 1 && !error)
    	{
    		cout << answer << endl;
    	}
    	else if(!error)
    	{
    		cout << "Error in input." << endl;
    	}
    }
    
    
    
    int main(int argc, char* argv[])
    
    {
    	if(argc != 2)
    	{
    		cout << "Must enter a file to evaluate at the command line." << endl;
    	}
    	
    	fstream in;
    	in.open(argv[1], ios::in);
    	string line, word;
    	cout.precision(10);
    	
    	if(in.good())
    	{
    		while(getline(in, line))  //get lines
    		{
    			vector<string> words;
    			cout << "> " << line << endl;
    			
    			while(line != "") //while line is non-empty, parse line into words
    			{
    				size_t found = 0;				//find space char
    				found = line.find_first_of(" ");
    				if(found < line.size())
    				{
    					word = line.substr(0,found);		//create word based on substring of line
    					words.push_back(word);			//add word to the vector
    					line = line.substr(found+1);		//remove word from line
    				}
    				else  						//no more whitespace - add last word
    				{
    					words.push_back(line);
    					line = "";
    				}
    			}
    			
    			rpn(words);		//call rpn to process the words
    			//cout << endl;
    		}
    	}
    	else
    	{
    		cout << "Error opening file." << endl;
    	}
    	in.close();
    	
    
    	return 0;
    
    }
    output:
    Code:
    chris@chris-desktop:~/Code/Projects/Challenge 11$ ./driver test
    > 3 4 +
    7
    > 10 3 /
    3.333333333
    > 2 5 ^
    32
    > 10 2 %
    0
    > 24 12 3 + 4 % / 6 - 4 * 3 ^
    512
    > 10 2 2 % /
    Dividing by zero!
    > 10 + 10
    Error in input.
    > aw4ojghsiu5esrgs56u7ikdyjdt drthisu 5 hrtgh 5 5 +
    Error in input.
    > 45 6 + / & 4
    Unrecognized token.

Page 1 of 3 123 LastLast

Bookmarks

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •