Parse an Expression to its components and sub components

Question

I need to parse an expression such as: neg(and(X,Y))

I need it to come out with the Abstract Stack Machine Code Such as for the example above:

LOAD X;
LOAD Y;
EXEC and;
EXEC neg;

But for now the machine code is not an issue, how can i parse / break up my input string of an expression into all its sub expressions?

I have tried to find the first bracket and then concat from that to the last bracket but that then gives isuess if you have a inner expression?

code that i have tried: (please not it is still very much in the development phase)

private boolean evaluateExpression(String expression) {

    int brackets = 0;
    int beginIndex = -1;
    int endIndex = -1;

    for (int i = 0; i < expression.length(); i++) {
        if (expression.charAt(i) == '(') {
            brackets++;

            if (brackets == 0) {
                endIndex = i;
                System.out.println("the first expression ends at " + i);
            }
        }
        if (expression.charAt(i) == ')') {
            brackets--;

            if (brackets == 0) {
                endIndex = i;
                System.out.println("the first expression ends at " + i);
            }
        }
    }
    // Check for 1st bracket
    for (int i = 0; i < expression.length(); i++) {
        if (expression.charAt(i) == '(') {
            beginIndex = i;
            break;
        }
    }

    String subExpression = expression.substring(beginIndex, endIndex);
    System.out.println("Sub expression: " + subExpression);

    evaluateExpression(subExpression);

    return false;

}

I am just looking for a basic solution, It only has to do: and, or, neg

Answer 1

Actually if you want your parser to be strong enough to deal with most cases, you would like to use a tokenizer(java has a implemented tokenizer class) to token the string first, then try to recognize each expression, storing operands and operators in a tree structure, then evaluate them recursively.

If you only want to deal with some simple situations, remember to use recursion, that is the core part~

Answer 2

The expressions you are trying to parse are actually making a Context Free Language, which can be represented as a Context Free Grammer.

You can create a context free grammer that represents this language of expressions, and use a CFG parser to parse it.

One existing java tool that does it (and more) is JavaCC, though it could be an overkill here.
Another algorithm to parse sentences using a CFG is CYK, which is fairly easy to program and use.

---

In here, the CFG representing the available expressions are:

S -> or(S,S)
S -> and(S,S)
S -> not(S)
S -> x | for each variable x

Note that though this is relatively simple CFG - the language it describes is irregular, so if you were hoping for regex - it's probably not the way to go.

Answer 3

Parsing things like this is typically done using syntax trees, using some type of preference for order of operations. An example for what you have posted would be as follows:

Processing items left to right the tree would be populated like this

1arg_fcall(neg)
        2arg_fcall(and)
            Load Y                      
            Load X

Now we can recursively visit this tree bottom to top to get
Load X
Load Y
EXEC and //on X and Y
EXEC neg //on result of and