I am writing an interpreter and have come that far that I need to identify or-stataments( || ).
Just for fundamental analysis. The code is not a problem. Only the thinking here.

My problem is that I am not quite sure how I have to think. I know how it works if I write it in C++, how to use parantheses ((...)) and so. That is not a problem.
The problem I have now is to identify both sides of an or statment in words.
In order to do this I understand that I have to think in parantheses in any way.
For ex:

if any of either sides in this statement is true, the whole statment is true. This is easy.
What I will do here is to create 2 .txtfiles with each statement because this gives 2 alternatives.
m > m2 || n > n2

A worse example will be if I put an && and an || to it like this with parantheses ((...))
Now the or statement wont have the same meening as above. This will also give 2 alternatives regarding the || statement but the whole statement will only create 1 file.
(m > m2 && (n > n2 || o > o2))

I am not sure if the idéa is cathed.
I am doing some examples below.
I might be interested to catch some fundamental idéas to how to think here.
I am quite stuck.
I have to find a red line to follow that will work for all possible scenarios.
For all these examples. 2 scenarios/colors can be true but how to identify one || from the other || to be more sure I will think right.

//Clean statement with one ||
((m > m2 && n > n2) || (o > o2 && p > p2)) 


//Added one more ||
((m > m2 && (n > n2 || o > o2)) || (p > p2))



//Added 2 ((...)) for the Whole statement
((((m > m2 && (n > n2 || o > o2)) || (p > p2))))


//Added  1 (..) for first || statement
((((m > m2 && ((n > n2 || o > o2))) || (p > p2))))

>My problem is that I am not quite sure how I have to think.
Think in terms of an expression tree, just like any other expression. The only difference here is accurately handling short-circuiting on top of precedence.

>> Think in terms of an expression tree

Thanks... I am trying to find a way to parse out the or-statements.
One way I thought I found out was to look for the first occurence of "||" in the string and then go backwords and count parantheses to be equal ((....)) and think of this as one possibility.
It makes sense for the second example that gives 2 possibilities but this thinking will not work for the first example because everything is needed to be true in that string/statement.
I might wonder if I am on the right track.

Gives 1 statement (Red has to be true)

(m > m2) || n > n2   &&  o > o2

Gives 2 statements (Red OR Green has to be true)

((m > m2 && (n > n2 || o > o2))   ||   (p > p2))

>My problem is that I am not quite sure how I have to think.
Think in terms of an expression tree, just like any other expression. The only difference here is accurately handling short-circuiting on top of precedence.

Looks to me like you need a way to identify the start and end of a statement. Looks to me like a new statement is initiated within the examples provided by any of the following '(', &&, and ||. There may be other triggers to recognition of a new statement as well no demostrated in the posted examples, such as the first char after a ';' if it's not a '\', etc.

Likewise the end of statement may be any of the following: ')', &&, ||, or ';'

This:

(m > m2 && (n > n2 || o > o2))

would then map to something like this;

a
         /    \
       /        \
     b           c
                 / \
                d   e

where:
a = m > m2 && (n > n2 || o > o2)
b = m > m2
c = n > n2 || o > o2
d = n > n2
e = o > o2

Thanks Lerner... I have tried to really understand the logic. I do understand that I have to "break down" the whole statement in someway but I am not sure of what has priority over others.
I will take an example where I get stuck.

a > a2 && b > b2

&&

(((c > c2 || d > d2)
&&
(e > e2 || f > f2))

||

((g > g2 || h > h2)
&&
(i > i2 || j > j2)))

&&

k > k2 && l > l2

My first question is: When parsing this out to make an "Expression Tree", do you read this from Start to End like you read it or do you find priorities as ((..Longest distance between Equal lot of parantheses ..)) parantheses etc...

If I start out to read from start to end with the example above. The first is easy:
a > a2 &&
b > b2

Then I got problem to understand what to do. I understand when looking at it that Either of the green parts has to be true and this I can identify by finding equal lot of parantheses.
Then if Either of the green areas is true then:
k> k2 &&
l > l2

My second question is that if I only would have statements with && wihout parantheses ex:
k> k2 &&
l > l2

I could save these into a vector vec[1] and run this through my interpreter wich do works fine now.
My question here is how I will put all the statements that in this case are green. Will I use 2D, 3D vector for scenarios like this or how do the procedure work.
I am quite confused.
The mainquestion is how to build an expression tree. Do I have to read from left to right and understand what areas is together (((....))) and what have priorities over others like for math: * has priority over + etc...

Thank You!


Looks to me like you need a way to identify the start and end of a statement. Looks to me like a new statement is initiated within the examples provided by any of the following '(', &&, and ||. There may be other triggers to recognition of a new statement as well no demostrated in the posted examples, such as the first char after a ';' if it's not a '\', etc.

Likewise the end of statement may be any of the following: ')', &&, ||, or ';'

This:

(m > m2 && (n > n2 || o > o2))

would then map to something like this;

a
         /    \
       /        \
     b           c
                 / \
                d   e

where:
a = m > m2 && (n > n2 || o > o2)
b = m > m2
c = n > n2 || o > o2
d = n > n2
e = o > o2

I'd read it start to finish. Each && and || has to have one and only one lhs and rhs that both evaluate to true or false. However, each lhs and rhs may have their own subexpressions. Subexpressions are best separated visually by ()s, and ()s can be used to force precedence. Let's take this:
(m > m2 && (n > n2 || o > o2))

The first char is ( so that means we have a new expression. Let's call it a. That also means that a has an lhs, lets call it b, and an rhs, lets call it c. The next char is m so it is the start of b and b extends until the first & is found. c starts with the first char after the second & it's another ( meaning c has an lhs, let's call it d, and an rhs lets call it e. In this case d starts immediately after the second ( and runs until the first |. Then e starts after the second | and runs until the first ). when the first ) is found it signifies the end of the subexpression b and then there's a second ) that ends the expression a.

What I might do was let a be the && and b be the ||. That way all the inner nodes would be logic operators and all the leaves would be subexpressions with the entire tree being a single overarching expression. To solve the expression I'd find the longest path an inner node and substitute the result of the expression using the two leaves and the logic operator. I'd delete the leaves as they are used. With each deletion I'd go back to the root and repeat the search for the longest path and redo the expression until there's only a root node.

I have to say this is all theoretical. I've never actually done this. That is, this post is how I'd go about solving the problem, though I've not actually solved it. Good luck on whatever approach you elect to take.

Member Avatar for iamthwee

Another alternative would be to use a stack and apply a similar approach to the shunting yard algo.

Member Avatar for iamthwee

If you're interested send me a PM, I have some code that might be of use based on a similar code I used to evaluate simple maths statements.

Thanks. I have come up with something similar to what you explained. I am doing a for loop where I reading the string from left to right and takes all possible scenarios in considiration.
I am looking for greatest distance of ((...)) as priority and then forward this and parses this down to subexpressions. Also looking for "&&" and "||" to have different rules.
I think I could be on the right track.
Then I delete this from the whole statement and again begin to read the remaining string from left to right until there is nothing left.
The loop will hopefully in the end work for "(" ")" and "&&" and "||" and put them in a correct line ready for feeding the interpreter with parsed statements.
It will take a while to finish it though. Are you interested to get the loop when it´s hopefully finished, I will send it. Just tell :)
Thanks

I'd read it start to finish. Each && and || has to have one and only one lhs and rhs that both evaluate to true or false. However, each lhs and rhs may have their own subexpressions. Subexpressions are best separated visually by ()s, and ()s can be used to force precedence. Let's take this:
(m > m2 && (n > n2 || o > o2))

The first char is ( so that means we have a new expression. Let's call it a. That also means that a has an lhs, lets call it b, and an rhs, lets call it c. The next char is m so it is the start of b and b extends until the first & is found. c starts with the first char after the second & it's another ( meaning c has an lhs, let's call it d, and an rhs lets call it e. In this case d starts immediately after the second ( and runs until the first |. Then e starts after the second | and runs until the first ). when the first ) is found it signifies the end of the subexpression b and then there's a second ) that ends the expression a.

What I might do was let a be the && and b be the ||. That way all the inner nodes would be logic operators and all the leaves would be subexpressions with the entire tree being a single overarching expression. To solve the expression I'd find the longest path an inner node and substitute the result of the expression using the two leaves and the logic operator. I'd delete the leaves as they are used. With each deletion I'd go back to the root and repeat the search for the longest path and redo the expression until there's only a root node.

I have to say this is all theoretical. I've never actually done this. That is, this post is how I'd go about solving the problem, though I've not actually solved it. Good luck on whatever approach you elect to take.

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.