String Formula to Integer

[Kranar]

Hello, does anyone have information or a link to a place where I can learn how to take an entire formula written as a string, and convert it into an integer?

For example a function called Convert that takes works something like...

CString formula = "5 + 3*6 - (2+6)^5";
int x = Convert(formula);

And Convert() evaluates the entire string and returns a value.

Any help would be greatly appreciated, thanks.

[twanvl]

1. Look for the operator with the LOWEST precedence in the string, not inside parenthesis (keep a variable with the nesting level, if '(' level++, if ')' level--)
2. Run the Convert function on everything before the operator, and everything after the operator, preform the operation on those two results.
3. If there is no operator found at step 1 you either have a expression in parenthesis, remove the parenthesis, and call Convert on that string.
If there are no parenthesis you have a number (or if you want to extend your parser later on, a named variable) you can convert it to an int (std::stringstream, boost::lexical_cast, atio)

This is not the fastest way to do it, but it is the easiest. (You could also write a function that uses no recursion, and keeps a stack of partialy evaluated values. Such an algorithm will be 10 times as long and complex)

[Kranar]

The only problem with such a method would be... what if I have multiple operators? How do I handle it then?

Referring to the example I posted, there are 5 operations being performed, how would I keep track of the algorythm handling the brackets first, then exponentiating the bracket, then multiplying and then adding? What about brackets within brackets and so on...

[twanvl]

The algorithm would work something like:

Covert("5 + 3*6 - (2+6)^5")
    step 1-> the '+' at position 2, split into "5" and "3*6 - (2+6)^5".
    a=Convert("5")
        returns 5
    b=Convert("3*6 - (2+6)^5")
        lowest precedence: '-' at position 4
        a=Convert(3*6)
            lowest precedence: '*' at pos 1
            a=Convert("3")
                returns 3
            b=Convert("6")
                returns 6
            returns a*b  (which is 18)
        b=Convert("(2+6)^5)")
            lowest precedence: '^' at pos 5
            a=Convert("(2+6)")
                in parenthesis, remove
                returns Convert("2+6")
                    lowest precedence: '+' at pos 1
                    a=Convert("2")
                        returns 2
                    b=Convert("6")
                        returns 2
                    returns a+b (which is 8)
            b=Convert(5)
                returns 5
            returns a^b (which is 32768)
        returns a-b (which is -32750)
    returns a+b (which is -32745)

The key is that the functions is recursive, it calls itself to calculate sub-expressions

[Kranar]

That pseudocode should be very... very helpful.

I'll try and implementing it into my scripting language, thanks a lot.

[Kranar]

Well I got to work on it, and it does have one BEDMAS problem.

Since the algorythm splits formulas into 2 sections, and then splits the right section of the formula again into 2 sections, and keeps on repeating until no sections are left, what happens is it messes up subtraction and addition.

For example, a string like "5 - 1 + 5" should work out to 9 using BEDMAS, but what the algorythm seems to be doing is:

convert(5 - 1 + 5)

           split into "5" and "1 + 5"
           a = convert("5")
                  returns 5
           b = convert("1 + 5")
                       split into "1" and "5"
                       a = convert("1")
                              returns 1
                       b = convert("5")
                              returns 5
                  returns (a + b) which is 6
          returns (a - b) which is -1

[Zaei]

Build an expression tree. Leaf nodes contain values, non-leaves contain operators. Use an in-order traversal to evaluate.

Z.

[twanvl]

If you take the last operator with the lowest precedence (+ and - have equal precedence), instead of the first, it should work.

[kedaman]

have two stacks, an operand and an operator stack. traverse the string from left to right. push operands on the stack, push operators on the operator stack, when encountering operators with lower precedence, a close parentesis or the end of the string, pop the operator and the amount of operands it requires and push them alltogether onto the operand stack until precedence is equal or higher, respective a start parentesis is found, as well as the start of the string. Ex:
1+2*(3+4)+5
[1][]0
[1][+]1
[1,2][+]1
[1,2][+,*]2
[1,2][+,*,(]0
[1,2,3][+,*,(]0
[1,2,3][+,*,(,+]1
[1,2,3,4][+,*,(,+]1
[1,2,4 3 +][+,*]2 (right parentesis found)
[1,3 4 + 2 *][+]1 (lower precedence)
[3 4 + 2 *1 +][]1 (end of string)
The evaluation can be done at these stages, but if you're writing a script and need variables, using postfix notations reduce the runtime load
3 4 + 2 *1 + is a postfix expression and is evaluated easily using a single operand stack, as precedence and parentesis are irrelevant.

[CornedBee]

But infix is more intuitive for the user.

[parksie]

Depends. Some people are used to stack-based calculators.

Although they're usually older people though

[kedaman]

I'd say it depends how you're taught, it would be unintuitive but "real" oop would 3+4 be math.aritmethic.plus(math.aritmethic.three,math.aritmethic.four)

[CornedBee]

We're not talking real OOP here, we're talking about practical uses (or did I miss something?)

[kedaman]

I know, but I like to do that sort of comments on OOP anyway
If people were taught postfix math in school they'd find infix very hard to comprehend, with precedence and parentesis and everything.

[CornedBee]

But infix is the way we talk, and it's not going to change.