Back to math

[Lord_Rat]

I posted a little while ago about how to perform basic mathematics on user-entered formulae and found that I can use System.Reflection to compile them and then execute the compiled code.

It turns out that the Web server I will be hosting my project does not allow System.Reflection (Access Denied). Which is good idea, really.

But it leaves me back to my original question...

How can I have a box (say a TextBox) where a user can enter a basic mathematical formula, like for example:

(6 + 5 * 2) * 2

And then feed that in to my program and it spits out the answer (32).

I had hoped at one point there was a Math.Eval function. There isn't.

So I am toying with the possibility of writing functions to handle all the math but every time I start on that, I realize three things:

1) It is a lot of work
2) It is a lot of work
3) It will require a different data structure than a simple array list and I have yet to find an appropriate structure.

So, I am placing the problem out on the public domain for responses/debate and the offchance that someone can just say "Oh yeah, just do X Y Z" and it will fix my issue.

[Lord_Rat]

Basically what I am thinking I am going to have to do is two fold:

First, find all parenthesis and start recursion on each set until I am at the innermost set.

Then, rewrite the equation using order of operations in to a literal left-to-right equation. Once I do, perform left-to-right math.

Thus, if the equation was:

3 + 5 * 2

It would internally be rewritten as:

5 * 2 + 3

Then just hit it left-to-right.

I am considering how I would write that.

[drpcken]

I am considering how I would write that.

You and me both

I would start by turning the equation into a string so you could manipulate it by pulling everything between parenthesis first and doing the math.

Wow the more I think of it the more complex it gets.

[nkad]

You need to parse the equation entered by the user, store it in a tree, then run through the tree and preform the calculation. I never done this before myself, so I am going to write some code to do it.

Edit: Recursion might work for simple equations, as Loard_Rat said.

[nkad]

On second thought 100% pure recursion isn't the way to go. It might be possable, but it would be a pain to code. The symbols and numbers should be arranged in a tree first. But anyway, here is code I wrote that will parse through the parens. Other then that, it does nothing else.

    Sub Main()
        Dim strEq As String
        Dim s As New Stack
        ParseEquation("(((3*5))(2+2)", 0, s)
    End Sub

    Function ParseEquation(ByVal eq As String, ByVal i As Integer, ByVal s As Stack) As Decimal
        Dim n As Integer

        If eq.Chars(i) = "(" Then
            s.Push("(")
            ParseEquation(eq, i + 1, s)
        Else
            n = i
            While eq.Chars(n) <> ")" Or n > eq.Length
                n += 1
            End While
            s.Pop()
            If s.Count <> 0 Then
                ParseEquation(eq, n + 1, s)
            End If
        End If
    End Function

Here is an example of how an equation could be arranged in a tree.

[Wokawidget]

Does this help:

http://www.vbdotnetheaven.com/Upload...f-bad8d38a411d

Oh, and it's Maths not Math

Woof

[SeanGrebey]

Basically what I am thinking I am going to have to do is two fold:

First, find all parenthesis and start recursion on each set until I am at the innermost set.

Then, rewrite the equation using order of operations in to a literal left-to-right equation. Once I do, perform left-to-right math.

Thus, if the equation was:

3 + 5 * 2

It would internally be rewritten as:

5 * 2 + 3

Then just hit it left-to-right.

I am considering how I would write that.

What happens if it is 3 - 5 * 2? Reordering it

5 * 2 - 3 doesn't work.

I think you are going to have to break it down first by parenthesis and then by order of operations without reordering it, and then resolve up. Basically find the highest order single mathmatical operation, perform it, and then find the next highest, and perform it. I don't think you are going to be able to do multiple operatiosn at a time.

[Wokawidget]

you would have to look at a - as a +-. ie:

3 - 5 * 2
= 3 - (5 * 2)
= 3 + -(5 * 2)
= -(5 * 2) + 3

Woka

[Lord_Rat]

Yeah I really messed up the example didn't I?

The tree that was shown above is a lot along the lines of what I think I have to do. But every time I start with the data structure, I realize how much it is kicking my lil rat tail...

[SeanGrebey]

It's probably not the best way, but if I was going to do it, I'd create an object that represents an expression, and attach an ArrayList or a linked list to it or something that represented each part of the expression as the same type of object, and so on until the expression was broken down to the lowest elements, and I'd sort the list by order of operations. Then when I was evaluating the expression, I'd start of with the first child object, and follow the children all the way down to the lowest level, do all those operations, then float up to the next level, 2nd object, and follow the tree down again.

So: 4 + (5 * 7) / 3

MasterObject.Expression = "4 + (5 * 7) / 3"
MasterObject.SubExpressions(0) = (5 * 7)
MasterObject.SubExpressions(1) = MasterObject.SubExpressions(0) / 3
MasterObject.SubExpressions(2) = MasterObject.SubExpressions(0) + 4

Or a More complex:

10 * (7 + 4 / 2) - 13

MasterObject.Expression = "10 * (7 + 4 / 2) - 13"
MasterObject.SubExpressions(0) = (7 + 4 / 2)
MasterObject.SubExpressions(0).SubExpressions(0) = 4 / 2
MasterObject.SubExpressions(0).SubExpressions(1) = MasterObject.SubExpressions(0).SubExpressions(0) + 7
MasterObject.SubExpressions(0) = MasterObject.SubExpressions(1) * 10
MasterObject.SubExpressions(0) = MasterObject.SubExpressions(2) - 13

So basically you just order your children by mathimatical order of operation, and then run down the tree. So we start at child Object 0.

Object 0 - > Have children? Yes, Go down one
Object 0, Object 0 -> Have Children, No? Evaluate:
Object 0, Object 0 = 2
Any other elements in this array? Yes
Object 0, Object 1 = 9
Any other elements in this array? No
So
Object 0 = 9
Any other elements in this array? Yes
Object 1 = 90
Any other elements in this array? Yes
Object 2 = 77
Any other elements in this array? No

Expression = 77

[Lord_Rat]

I watered it down some.

I am using recursion on parenthesis until I get to a parenthetical set at the innermost level.

Then, I have a list of operands in order-of-operations order. And I loop through the equation reducing the equation by performing each operation in turn until I end up with a single number, then go back out one level.

Still coding, but this level of simplicity is at least getting me somewhere.

I might add functions in at a later date, but not for now. For now, it is straight math (or maths for you singular-impaired folk).

[Lord_Rat]

[...]

Not to be mean (certainly not).

But that seems like quite the headache. I hurt even thinking about it ><

[SeanGrebey]

Heh, I didn't say it was the best way, but it would work and the coding would be pretty easy. Flow down to lowest level child, do math across, pop answer up.

[Lord_Rat]

That's pretty close to what I have going now.

In fact, I have it working if I don't use parenthesis already!

Finishing up getting parens to work and then Ill post it.

And once I got going with my latest train of though, I 'sploded from there.

[SeanGrebey]

Treat what is in the parans like a stand alone expression, apply your expression logic to it, and then just spit out a result to plug back in.

[Lord_Rat]

Yep. That's what Im doin! =)

[SeanGrebey]

Post your code when you are done...

[Lord_Rat]

You betcha =) I am slacking a bit. I read Boards while I program, so I would have been done by now except for that.

Heh. =)

But Ill have it done shortly.

[Lord_Rat]

Well, I beleive I got it and overall, the code is incredibly simple once boiled down to its root elements, coupled with the power of regular expressions. (And if I can pat myself on the back here, many years of experience with programming didn't hurt either)

using System;

namespace Utility
{
	public class Math
	{
		/// <summary>
		/// Summary description for Class1.
		/// </summary>
		
		public static string Eval(string sInput)
		{
			string sWorking = sInput;

			while(sWorking.IndexOf("(") > -1)
			{
				sWorking = sWorking.Replace("(" + GetMatchedSet(sWorking) + ")", Eval(GetMatchedSet(sWorking)));
			}

			sWorking = EvalInnermost(sWorking);

			return sWorking;
		}

		private static string GetMatchedSet(string sInput)
		{
			int iDepth = 0;
			int iOffset = sInput.IndexOf("(");
			string sWorking = "";
			int i = 0;
			for(i = iOffset ; i < sInput.Length ; i++)
			{
				if(sInput.Substring(i, 1).CompareTo("(") == 0) iDepth++;
				if(sInput.Substring(i, 1).CompareTo(")") == 0)
				{
					iDepth--;
					if(iDepth == 0) break;
				}
			}

			if(iDepth != 0) throw new ApplicationException("Parenthesis mismatch: " + sInput);

			sWorking = sInput.Substring(iOffset + 1, (i - iOffset) - 1);
			return sWorking;
		}

		private static string EvalInnermost(string sInput)
		{
			string[] sOperands = {"^", "*", "/", "+", "-"}; //operands in order-of-operations order

			string sWorking = sInput;
			for(int i = 0 ; i < sOperands.Length ; i++)
			{
				sWorking = ReduceOperand(sWorking, sOperands[i]);
			}
			return sWorking;
		}
		
		private static string ReduceOperand(string sInput, string sOperand)
		{
			string sRegEx = @"([\-\+]{0,1}\d+\.{0,1}\d*)\s*\" + sOperand + @"\s*([\-\+]{0,1}\d+\.{0,1}\d*)";
			bool bDone = false;
			string sWorking = sInput;

			while(!bDone)
			{
				System.Text.RegularExpressions.Regex oRE = new System.Text.RegularExpressions.Regex(sRegEx);
				if(oRE.IsMatch(sWorking))
				{
					System.Text.RegularExpressions.Match oMatch = oRE.Match(sWorking);
					string sReplacement = oMatch.Value;
					string sResult = PerformMath(oMatch.Groups[1].ToString(), oMatch.Groups[2].ToString(), sOperand);
					sWorking = sWorking.Replace(sReplacement, sResult);
				}
				else
				{
					bDone = true;
				}
			}
			return sWorking;
		}

		private static string PerformMath(string sVal1, string sVal2, string sOperand)
		{
			double iVal1 = double.Parse(sVal1);
			double iVal2 = double.Parse(sVal2);
			switch(sOperand)
			{
				case "^":
					return (System.Math.Pow(iVal1, iVal2)).ToString();
				case "*":
					return (iVal1 * iVal2).ToString();
				case "/":
					return (iVal1 / iVal2).ToString();
				case "+":
					return (iVal1 + iVal2).ToString();
				case "-":
					return (iVal1 - iVal2).ToString();
			}

			throw new ApplicationException("Arithmetic not supported: " + sOperand.ToString());

		}
	}
}

[Lord_Rat]

Notice that if something is not a mathematical expression, only the parts that are mathematical gets reduced. No errors get thrown.

Thus:

I have 6 + 2 eggs plus 5 + 3x Herbs.

Gets reduced to:

I have 8 eggs plus 8x Herbs

So don't be trying to use it for differential calculus, you hear?

[cfisher]

You may have already solved this, but I'll give my two cents anyway.
What about reading through the math string and as each parentheses is encountered, do a count to see how many there are. If there are 4 i.e. ((3*2)-5)+3, the you would know that 1 and 4 go together and 2 and 3 go together. Using that, you would know your staring point and be able work outwards to solve the equation. I haven't worked it out in code and it is a simple equation, but I don't see the function being that difficult.