CODEWITHSUNDEEP
javaparsingexpression
dcfc_rph
dcfc_rph

Reputation: 309

Expression parsing using binary operators

I'm trying to figure out ways to parse an expression that uses all binary operators. Each operator is surrounded by exactly one set of parenthesis, such that:

5x^2 + 3x + 2

would be

((5*(x^2))+((3*x)+2))

and is taken as an args[] argument (more importantly, it is given as a String).

I'm recursively breaking this down, where each recursion breaks down the left part of the top binary operator and call the recursion with that expression as an argument, then again with the right. The base case is when the expression being passed contains no operators.

The problem I'm having is appropriately parsing the left side from the right side. I am trying to develop a way based upon a Scanner that counts the number of parenthesis counted overall, but can't seem to determine a final solution. Anyone have an idea how to parse this correctly in order to pass it as an expression to the recursive method.

P.s. - Language I am using is Java

EDIT::::

I am using this parser as a part of a GUI graph plotter, so I would set the variable (x) based on what value of the x-axis I am currently looking to generate on the GUI graph. So, the expression being parsed within the program (as shown in the second code tag above) would be broken down and operated on to produce a final "y" value that would correlate to the position on the window where a small dot would be used to represent that point on the line of the graph.

Maybe this will better explain how I am trying to use this.

Upvotes: 2

Views: 2173

Answers (3)

Henrique Rocha
Henrique Rocha

Reputation: 1737

What you want to implement is a simple recursive descent parser, which means that each production of your grammar will turn into a recursive function probably similar to what you're currently doing.

I don't know if you're familiar with the BNF syntax but here is one possible grammar for your language of binary operators. I'm omitting the power operator, which I leave for you to implement.

Expression ::= Expression + Term
Expression ::= Expression - Term
Expression ::= Term

Term ::= Term * Factor
Term ::= Term / Factor
Term ::= Factor

Factor ::= number
Factor ::= ( Expression )

With that you can see that you're defining an Expression by using an Expression, hence the use of recursive functions.

Please read this Wikipedia link and you'll immediately see how to implement what you want. http://en.wikipedia.org/wiki/Recursive_descent_parser

Upvotes: 1

corsiKa
corsiKa

Reputation: 82579

I would start with an element class

interface Element {

}

And two elements

abstract class Operator implements Element {

    Operand operate(Operand a, Operand b);

}

class Operand implements Element {
    int value;
    Operand(int value) { this.value = value; }
}

Now you can create your Operator factory

class OperatorFactory {
    Operator createOperator(String symbol) {
         if("+".equals(symbol)) 
             return new Operator() {
                 Operator operate(Operand a, Operand b) { 
                     return new Operand(a.value + b.value);
                 }
             };
         if("-".equals(symbol)) /* continued */
    }
}

Now you're able to make yourself a stack processor that recurs when you reach a "(" and operates when you reach a ")". I imagine the rest will be pretty trivial from there.

Upvotes: 2

Kashyap
Kashyap

Reputation: 17441

Is your problem with logic or code?

In your logic, only issue I see is the precedence and associativity should also be considered (depending on the operator).

If the problem is with code, can you post the code? Also an example with teh expected output vs actual output would help so I don't have to put it in eclipse and run it myself.

Upvotes: 0

Related Questions