Problem description:
-----------------------------------------
infix expression: a+b*c+d*e+f
its posish notaion：+++a*bc*def
Here*means&&，+means||，
abcdef are operands，all boolean with value 0 or 1
So a+b*c+d*e+f is a logic expression
Among logic evaluation, there are 2 points:
1.short circuit:
if a is 1，then +a*bc is 1，*bc is not need to be evaluted
if b为0，then *bc is 0, c can be ingored
2.polish expression with N operators and N+1 operands
If the expression is very long, shore circuit can save much time,
but how to make use of short circuit?
--------------------------------------------------------------------------
The method I came out：
-----------------------------------------
set number of operator:m，number of operands:n，
a complete polish notation logic expression，should be：n = m + 1,
so the value of m and n can be used to divide the logic expression into independent small expessions
for +++a*bc*def, small blocks are such like: *bc *de f
then set an array like next[] to store the pos of first member of the small expression:
next[0] = 4, next[1] = 7, next[2] = 10
then during the evaluation program:
push +++, if a is 1 then result of +a??????? is 1,
then according array next[], the block after +a should be from 4 to (7-1), which can be ingored to evaluate.
This is the only method I came out, to set an auxiliary array, then: more space, shorter time
However, my boss wants a more fast algorith which should be published as paper or anything else likely.
Anyone else know a more efficient algorithm? any paper?
Thank you very much!
-----------------------------------------
infix expression: a+b*c+d*e+f
its posish notaion：+++a*bc*def
Here*means&&，+means||，
abcdef are operands，all boolean with value 0 or 1
So a+b*c+d*e+f is a logic expression
Among logic evaluation, there are 2 points:
1.short circuit:
if a is 1，then +a*bc is 1，*bc is not need to be evaluted
if b为0，then *bc is 0, c can be ingored
2.polish expression with N operators and N+1 operands
If the expression is very long, shore circuit can save much time,
but how to make use of short circuit?
--------------------------------------------------------------------------
The method I came out：
-----------------------------------------
set number of operator:m，number of operands:n，
a complete polish notation logic expression，should be：n = m + 1,
so the value of m and n can be used to divide the logic expression into independent small expessions
for +++a*bc*def, small blocks are such like: *bc *de f
then set an array like next[] to store the pos of first member of the small expression:
next[0] = 4, next[1] = 7, next[2] = 10
then during the evaluation program:
push +++, if a is 1 then result of +a??????? is 1,
then according array next[], the block after +a should be from 4 to (7-1), which can be ingored to evaluate.
This is the only method I came out, to set an auxiliary array, then: more space, shorter time
However, my boss wants a more fast algorith which should be published as paper or anything else likely.
Anyone else know a more efficient algorithm? any paper?
Thank you very much!