Algorithms proof

This is a discussion on Algorithms proof within the C Programming forums, part of the General Programming Boards category; First of all there are a variety of way to solve equations like the ones you are quoting. One idea ...

  1. #16
    Super Moderater.
    Join Date
    Jan 2005
    Posts
    374
    First of all there are a variety of way to solve equations like the ones you are quoting.


    One idea would be to use a stack to solve your expression.
    http://www.spsu.edu/cs/faculty/bbrow...tures/postfix/
    http://www.qiksearch.com/articles/cs...ix-evaluation/

    Another idea, would be to use a binary tree to solve your expression.

    Take for example :
    Code:
    2+2*(11-3)

    This would be parsed as such in a binary tree:

    Code:
               +
              / \
             *   2
            / \
           2   -
              / \
             11  3
    And evaluated from the bottom upwards. Meaning that a post order traversal of the tree will evaluate the expression correctly.
    I.e in postfix notation.

    http://math.hws.edu/eck/cs225/s03/binary_trees/

    If I were you I would seriously consider looking into using either the stack or a binary tree to do this. Ok, these data structures are not trivial but this is probably the only reliable way to obtain accurate calculations.

    I've not seen your code, but it sounds as if you have done the same using multiple classes and case conditions. In short this will probably fail at some point in the long run. On the other hand, you mentioned briefly using a linked list, so you may not be too far from a reliable solution.

    Good luck
    Last edited by treenef; 11-16-2005 at 04:01 AM.

  2. #17
    aoeuhtns
    Join Date
    Jul 2005
    Posts
    581
    Quote Originally Posted by Prelude
    >Proform a mathimatical proof.
    First let me say that I don't think much of mathematical proofs. The only thing you prove is that you can bend reality to your will with math. I could use mathematics to correctly prove that the sky is always a nice shade of lilac, but that doesn't make it true.
    That sounds more like philosophy than mathematics.

  3. #18
    Registered User
    Join Date
    Aug 2002
    Location
    Hermosa Beach, CA
    Posts
    446
    Okay, what you need to think of is general classes of problems.

    1) Can it solve basic cases like:
    1+1+7+3-2

    2) Does it correctly handle order of operation cases without parens:
    1+7*3-4

    3) Does it handle order of operations for simple paren cases:
    3*(2+4)-5

    4.) Does it handle multiple paren cases, not nested:
    (2+5) * (4+1)

    5) Does it eat white space:
    (2 + 5) * 4

    6) Does it handle nested parens:
    (2*((4+3)/(4-2))) * 9

    If I tested all these general cases, and it seemed to work, I would be satisfied. You could also consider making a unix-like interface to it, so that it reads expressions from standard input, and then writes the result to standard output. Then you could make a file that has many test cases in it, and it would be simple to run all of them--just cat the file and pipe it into your program, and then pipe your program's output into some other program that might verify the results are correct.
    The crows maintain that a single crow could destroy the heavens. Doubtless this is so. But it proves nothing against the heavens, for the heavens signify simply: the impossibility of crows.

  4. #19
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,796
    >That sounds more like philosophy than mathematics.
    It's all pretty subjective, ne?
    My best code is written with the delete key.

Page 2 of 2 FirstFirst 12
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Sorting algorithms, worst-case input
    By Leftos in forum C++ Programming
    Replies: 17
    Last Post: 06-15-2009, 01:33 PM
  2. Understanding formulas, shapes, algorithms etc
    By hardi in forum A Brief History of Cprogramming.com
    Replies: 26
    Last Post: 04-16-2007, 01:23 PM
  3. God
    By datainjector in forum A Brief History of Cprogramming.com
    Replies: 746
    Last Post: 12-22-2002, 11:01 AM
  4. relative strength of encryption algorithms (blowfish, des, rinjdael...)
    By duck-billed platypus in forum A Brief History of Cprogramming.com
    Replies: 3
    Last Post: 12-30-2001, 03:20 PM

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