Need help in RPN calculator

This is a discussion on Need help in RPN calculator within the C Programming forums, part of the General Programming Boards category; I developed a program that is an rpn calculator. For those who dont know what an RPN calculator is,it works ...

  1. #1
    Registered User Lost__Soul's Avatar
    Join Date
    Mar 2003
    Posts
    82

    Need help in RPN calculator

    I developed a program that is an rpn calculator. For those who dont know what an RPN calculator is,it works similar to assembly programming language. An input file would look like this:
    PUSH 1
    PUSH 2
    POP abc
    PUSH 2323
    ADD
    MUL
    POP xyz
    JUMP 2
    ...
    The program is working fine,i just have to improve efficiency. Im using fscanf to read each line and then i have a function that computes each command (ADD, MUL,...). The problem is with the JUMP function:
    In this example,the program would jump to line 2(PUSH 2). I have a program counter that stores the current line number. But, when i have to jump, 2 things can happen:
    1. The line is before the current line: i use rewind(file) then program counter =0, read the commands again until i find the one i want;
    2. The line is after the current line: in this case, i just keep reading lines until i find the one i want.
    This works,but its not very fast,specially in very large inputs. So,i was thinking in storing the commands in memory while i was reading then and then read the memory instead of the file. The only thing i dont know is what data struture should i use to store things in memory. My teachers talked about an hash table,ok, that would be good, i just dont have any idea of how to hash the lines. They also told me that inserting a line in each position of the array will eventually result in a segmentation fault(the inputs will have millions of commands).
    So, i hope someone could give some ideas!

  2. #2
    Registered User
    Join Date
    Feb 2003
    Posts
    595
    How 'bout an array (or a vector) of strings? You can load the commands sequentially into the array, and then you can jump directly to the one you need. Also, you can easily build in procedures to prevent jumping beyond the limits of the array.

  3. #3
    C++ Developer XSquared's Avatar
    Join Date
    Jun 2002
    Location
    Ontario, Canada
    Posts
    2,718
    >> (or a vector)
    This is C, not C++. No vectors.

    A linked list would work well here though.
    Naturally I didn't feel inspired enough to read all the links for you, since I already slaved away for long hours under a blistering sun pressing the search button after typing four whole words! - Quzah

    You. Fetch me my copy of the Wall Street Journal. You two, fight to the death - Stewie

  4. #4
    Registered User
    Join Date
    Feb 2003
    Posts
    595
    Sorry. Forgot where I was on the board.

    But I still like the array idea better than a linked list - allows for directly accessing the desired command. So, an array of pointers to char strings. Either declare an array of a fixed size long enough to accomodate some predetermined maximum number of commands, or use malloc to allocate an appropriate array size for the particular input file.

  5. #5
    C++ Developer XSquared's Avatar
    Join Date
    Jun 2002
    Location
    Ontario, Canada
    Posts
    2,718
    With this program you're stepping through the commands in order, so a linked list would be perfect. You don't need to jump around a whole lot.

    If you do decide to use an array, make sure you allocate it on the heap, not on the stack. Otherwise you will run outta memory fast.
    Naturally I didn't feel inspired enough to read all the links for you, since I already slaved away for long hours under a blistering sun pressing the search button after typing four whole words! - Quzah

    You. Fetch me my copy of the Wall Street Journal. You two, fight to the death - Stewie

  6. #6
    Registered User Lost__Soul's Avatar
    Join Date
    Mar 2003
    Posts
    82
    Theres no "predetermined maximum number of commands". Like i said, the array option will have a memory problem, billions of commands would require an array with billions of positions...And the linked list is not an option, since it would require to read everything in the list,which would take a lot of time.

  7. #7
    Registered User
    Join Date
    Mar 2003
    Posts
    143
    ... But if you implement a fifo buffer and limit the distance that you allow for jumps - maybe think about making jumps relative (assuming you have some kind of control over the language definition) so that the code you had becomes:
    Code:
    PUSH 1
    PUSH 2
    POP abc
    PUSH 2323
    ADD
    MUL
    POP xyz
    JUMP -6
    ...
    I know this limits how far you can jump, but to honest I consider that a good thing!
    DavT
    -----------------------------------------------

  8. #8
    Registered User Lost__Soul's Avatar
    Join Date
    Mar 2003
    Posts
    82
    Well, that would be good, but i cant limit the jump...

  9. #9
    Registered User Lost__Soul's Avatar
    Join Date
    Mar 2003
    Posts
    82
    The advantage of 2 and 4 is that you only parse the line once - assuming that you've separated the 'parse' from the 'execute' in your code.
    Ive parsed the line.

    Compared to what - keeping it all in a file and using lots of file commands (like fseek()) to shuffle backwards and forwards?
    Well, the list would have as many ~elements as the commands. Imagine i want to access the 1,500,000 command, i would have to read 1,499,999 commands before i find the one i want. The program shouldnt take more than 1 minute to return the result, so the list would be too slow.

    Will be a very big file!!!
    yup, its serious, how do i build a cache?

  10. #10
    Registered User Lost__Soul's Avatar
    Join Date
    Mar 2003
    Posts
    82
    This places an upper limit on the size of your file - simply reading a huge file will take a long time.
    Believe me,it doesnt...In my university we got used to find the most eficient solution, and since i was told that the program wont take more than a minute,even with the big files, i have to make it work like that.

    Ill do some search for caches and if i have any doubt ill post them here...

  11. #11
    Registered User Lost__Soul's Avatar
    Join Date
    Mar 2003
    Posts
    82
    Tried a search in google but found no "implementable" algorhitm...Can you give me some idea of what i have to do? i dont need any code, just some ideas. The cache would work similar to an hash table,right?

  12. #12
    Registered User Lost__Soul's Avatar
    Join Date
    Mar 2003
    Posts
    82
    Well,thnks a lot, this is way to advanced for a begginner like me so i have to read it carefully.

  13. #13
    Been here, done that.
    Join Date
    May 2003
    Posts
    1,157
    Another option is to
    1) read the entire file (or as much as is feasable),
    2) preprocess the file by adding each line (0th byte and every byte that follows a CRLF) to a pointer array
    3) change the preceeding CRLF to \0

    Now you have the file by line in memory. Your JUMP 2 then simply goes to the pointer array.

    For files that are too large to read in one pass, you'll have to work out how to process pages as mentioned previously.
    Definition: Politics -- Latin, from
    poly meaning many and
    tics meaning blood sucking parasites
    -- Tom Smothers

  14. #14
    C++ Developer XSquared's Avatar
    Join Date
    Jun 2002
    Location
    Ontario, Canada
    Posts
    2,718
    If there are 'billions' of commands, you're dealing with a multi-gigabyte file.

    Also, is a jump command dealt with once, then ignored? If not, if it is jumping to a position before itself, it will just go into an infinite loop.
    Naturally I didn't feel inspired enough to read all the links for you, since I already slaved away for long hours under a blistering sun pressing the search button after typing four whole words! - Quzah

    You. Fetch me my copy of the Wall Street Journal. You two, fight to the death - Stewie

  15. #15
    Registered User Lost__Soul's Avatar
    Join Date
    Mar 2003
    Posts
    82
    The jump can be conditional, for example, JUMPZERO number
    The program will only jump to line "number" if the top of the stack is 0. The JUMP is never ignored, so this kind of input file will not be tested(it would enter an infinite cycle).

    Im trying to solve the problem with fseek and with an array to store the position(in bytes) of each line. If this doesnt solve the effiency problem, then ill have to work with the cache thing.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. RPN calculator
    By bassist11 in forum C Programming
    Replies: 14
    Last Post: 03-02-2009, 10:37 PM
  2. GUI Calculator - Critique
    By The Brain in forum Windows Programming
    Replies: 1
    Last Post: 02-25-2006, 03:39 AM
  3. Calculator + LinkedList
    By maro009 in forum C++ Programming
    Replies: 20
    Last Post: 05-17-2005, 12:56 PM
  4. Need help with calculator program
    By Kate in forum C# Programming
    Replies: 1
    Last Post: 01-16-2004, 09:48 AM
  5. Replies: 2
    Last Post: 05-10-2002, 04:16 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21