How to get rid of unnecessary parentheses in mathematical expression

Question

Hi I was wondering if there is any known way to get rid of unnecessary parentheses in mathematical formula. The reason I am asking this question is that I have to minimize such formula length

if((-if(([V].[6432])=0;0;(([V].[6432])-([V].[6445]))*(((([V].[6443]))/1000*([V].[6448])
+(([V].[6443]))*([V].[6449])+([V].[6450]))*(1-([V].[6446])))))=0;([V].[6428])*
((((([V].[6443]))/1000*([V].[6445])*([V].[6448])+(([V].[6443]))*([V].[6445])*
([V].[6449])+([V].[6445])*([V].[6450])))*(1-([V].[6446])));

it is basically part of sql select statement. It cannot surpass 255 characters and I cannot modify the code that produces this formula (basically a black box ;) ) As you see many parentheses are useless. Not mentioning the fact that:

((a) * (b)) + (c) = a * b + c

So I want to keep the order of operations Parenthesis, Multiply/Divide, Add/Subtract.

Im working in VB, but solution in any language will be fine.

Edit

I found an opposite problem (add parentheses to a expression) Question.

I really thought that this could be accomplished without heavy parsing. But it seems that some parser that will go through the expression and save it in a expression tree is unevitable.

Zebe

aka Normalization to the Normal Form. this is used for example in the Nix interpreter, to cache semantically identical expressions (maximal sharing). as described by ThibThib, the only solution is to parse the expression, remove "noop" nodes, stringify. maybe you can use an existing system for Term Rewriting – Broder

Answer 1

You could strip the simplest cases:

([V].[6432]) and (([V].[6443]))

Becomes

v.[6432]

You shouldn't need the [] around the table name or its alias.

You could shorten it further if you can alias the columns:

select v.[6432] as a, v.[6443] as b, ....

Or even put all the tables being queried into a single subquery - then you wouldn't need the table prefix:

if((-if(a=0;0;(a-b)*((c/1000*d
+c*e+f)*(1-g))))=0;h*
(((c/1000*b*d+c*b*
e+b*f))*(1-g));

select [V].[6432] as a, [V].[6445] as b, [V].[6443] as c, [V].[6448] as d, 
    [V].[6449] as e, [V].[6450] as f,[V].[6446] as g, [V].[6428] as h ...

Obviously this is all a bit psedo-code, but it should help you simplify the full statement

Spano

Answer 2

If you are interested in remove the non-necessary parenthesis in your expression, the generic solution consists in parsing your text and build the associated expression tree.

Then, from this tree, you can find the corresponding text without non-necessary parenthesis, by applying some rules:

• if the node is a "+", no parenthesis are required
• if the node is a "*", then parenthesis are required for left(right) child only if the left(right) child is a "+"
• the same apply for "/"

But if your problem is just to deal with these 255 characters, you can probably just use intermediate variables to store intermediate results

T1 = (([V].[6432])-([V].[6445]))*(((([V].[6443]))/1000*([V].[6448])+(([V].[6443]))*([V].[6449])+([V].[6450]))*(1-([V].[6446])))))
T2 = etc...

Ultima

Answer 3

I know this thread is really old, but as it is searchable from google.

I'm writing a TI-83 plus calculator program that addresses similar issues. In my case, I'm trying to actually solve the equation for a specific variable in number, but it may still relate to your problem, although I'm using an array, so it might be easier for me to pick out specific values...
It's not quite done, but it does get rid of the vast majority of parentheses with (I think), a somewhat elegant solution.

What I do is scan through the equation/function/whatever, keeping track of each opening parenthese "(" until I find a closing parenthese ")", at which point I can be assured that I won't run into any more deeply nested parenthese.

y=((3x + (2))) would show the (2) first, and then the (3x + (2)), and then the ((3x + 2))).

What it does then is checks the values immediately before and after each parenthese. In the case above, it would return + and ). Each of these is assigned a number value. Between the two of them, the higher is used. If no operators are found (*,/,+,^, or -) I default to a value of 0.

Next I scan through the inside of the parentheses. I use a similar numbering system, although in this case I use the lowest value found, not the highest. I default to a value of 5 if nothing is found, as would be in the case above.

The idea is that you can assign a number to the importance of the parentheses by subtracting the two values. If you have something like a ^ on the outside of the parentheses (2+3)^5 those parentheses are potentially very important, and would be given a high value, (in my program I use 5 for ^).

It is possible however that the inside operators would render the parentheses very unimportant, (2)^5 where nothing is found. In that case the inside would be assigned a value of 5. By subtracting the two values, you can then determine whether or not a set of parentheses is neccessary simply by checking whether the resulting number is greater than 0. In the case of (2+3)^5, a ^ would give a value of 5, and a + would give a value of 1. The resulting number would be 4, which would indicate that the parentheses are in fact needed. In the case of (2)^5 you would have an inner value of 5 and an outer value of 5, resulting in a final value of 0, showing that the parentheses are unimportant, and can be removed.

The downside to this is that, (at least on the TI-83) scanning through the equation so many times is ridiculously slow. But if speed isn't an issue... Don't know if that will help at all, I might be completely off topic. Hope you got everything up and working.

Triennial

Answer 4

I'm pretty sure that in order to determine what parentheses are unnecessary, you have to evaluate the expressions within them. Because you can nest parentheses, this is is the sort of recursive problem that a regular expression can only address in a shallow manner, and most likely to incorrect results. If you're already evaluating the expression, maybe you'd like to simplify the formula if possible. This also gets kind of tricky, and in some approaches uses techniques that that are also seen in machine learning, such as you might see in the following paper: http://portal.acm.org/citation.cfm?id=1005298

Landeros

Answer 5

If your variable names don't change significantly from 1 query to the next, you could try a series of replace() commands. i.e.

X=replace([QryString],"(([V].[6443]))","[V].[6443]")

Also, why can't it surpass 255 characters? If you are storing this as a string field in an Access table, then you could try putting half the expression in 1 field and the second half in another.

Microcyte

Answer 6

You could also try parsing your expression using ANTLR, yacc or similar and create a parse tree. These trees usually optimize parentheses away. Then you would just have to create expression back from tree (without parentheses obviously).

It might take you more than a few hours to get this working though. But expression parsing is usually the first example on generic parsing, so you might be able to take a sample and modify it to your needs.

Vivyan