Thread: Algorithms proof

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

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.

>That sounds more like philosophy than mathematics.
It's all pretty subjective, ne?