CODEWITHSUNDEEP
c++
RoR
RoR

Reputation: 16482

Which Data Structure used to solve a simple math equation

When taking in a expression like (10+5*15) and following orders of operations.

How would one best solve a problem like this? What kind of data structure is best?

Thanks.

Upvotes: 5

Views: 5928

Answers (6)

Drahakar
Drahakar

Reputation: 6088

I'd go with Dijkstra's Shunting yard algorithm to create the AST.

Upvotes: 9

6502
6502

Reputation: 114569

If you need to simply compute the result of the expression that is available as a string then I'd go with no data structure at all and just functions like:

//
// expression ::= addendum [ { "-" | "+" } addendum ]
// addendum ::= factor [ { "*" | "/" } factor ]
// factor ::= { number | sub-expression | "-" factor }
// sub-expression ::= "(" expression ")"
// number ::= digit [ digit ]
// digit ::= { "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9" }
//

int calcExpression(const char *& p);
int calcDigit(const char *& p);
int calcNumber(const char *& p);
int calcFactor(const char *& p);
int calcAddendum(const char *& p);

where each function just accepts a const char * by reference that reads from it (incrementing the pointer) and returning as value the numeric value of the result, throwing instead an exception in case of problems.

This approach doesn't need any data structure because uses the C++ stack for intermediate results. As an example...

int calcDigit(const char *& p)
{
    if (*p >= '0' && *p <= '9')
        return *p++ - '0';
    throw std::runtime_error("Digit expected");
}

int calcNumber(const char *& p)
{
    int acc = calcDigit(p);
    while (*p >= '0' && *p <= '9')
        acc = acc * 10 + calcDigit(p);
    return acc;
}

If you need instead to write a compiler that transforms a string (for example including variables or function calls) into code or bytecode then probably the best solution is to start either using a generic n-way tree or a tree with specific structures for the different AST node types.

Upvotes: 0

Jerry Coffin
Jerry Coffin

Reputation: 490398

The usual data structure for this task is a stack. When you're doing things like compiling, creating an abstract syntax tree is useful, but for simple evaluation it's usually overkill.

Upvotes: 2

Chris Dennett
Chris Dennett

Reputation: 22731

It's in Java, but this seems to convert from infix to postfix, and then evaluates using a stack-based approach. It puts numbers onto the stack, reaches operators, and then pops the two numbers from the stack to evaluate them with the operator (x + / -).

http://enel.ucalgary.ca/People/Norman/enel315_winter1999/lab_solutions/lab5sol/exF/Calculator.java

The conversion is as follows:

  • Scan the Infix string from left to right.
  • Initialise an empty stack.
  • If the scannned character is an operand, add it to the Postfix string. If the scanned character is an operator and if the stack is empty
  • Push the character to stack.
    • If the scanned character is an Operand and the stack is not empty, compare the precedence of the character with the element on top of the stack (topStack). If topStack has higher precedence over the scanned character Pop the stack else Push the scanned character to stack. Repeat this step as long as stack is not empty and topStack has precedence over the character.
  • Repeat this step till all the characters are scanned. (After all characters are scanned, we have to add any character that the stack may have to the Postfix string.)
  • If stack is not empty add topStack to Postfix string and Pop the stack. Repeat this step as long as stack is not empty.
  • Return the Postfix string.
  • Evaluate the Postfix string.

Upvotes: 0

Tejs
Tejs

Reputation: 41256

Think about it for a second - what is an operator? Pretty much every operator (+, -, *, /) are all binary operators. Parenthesis are depth constructors; you move one level deeper with parenthesis.

In fact, constructing the tree of data you need to solve this problem is going to be your biggest hurdle.

Upvotes: 1

Daniel Lubarov
Daniel Lubarov

Reputation: 7924

Try parsing the expression using recursive descent. This would give you a parse tree respecting order of operations.

Upvotes: 4

Related Questions