best data strcuture for numeric parsing.
-
Hi, I've a assignment where I have to write a program that can parse and evaluate certain numerical expression like
sin(30)*5*log10(300)/6^2%5
Well, I've already done my research through reading articles on code project, there are very good examples on this topic. So I've decided to use STACK based infix to post-fix conversion and finally evaluating the post-fix expression again using stack. Right Now, I've a class called "Expression" that stores each expression viz. *, /, %, sin, cos, log, tan..and many more. Let say you've following post fix expression
10 20 + 2 ^ sin 56 % 5 *
In simpler term, its infix expression is
(sin((10 + 20)^2) % 56) * 5
Now, during evaluating post fix expression, you encounter operators viz. *, /, ^, %, then you pop two elements from stack and perform this operation and finally you get result. I've like 30 of these mathematical operators, each time these operator occurs in post fix expression (operator is just a character in string), I perform search like
if(operator == '*')
{
return var1 * var2;
}if(operator == '*')
{
return var1 * var2;
}if(operator == '/')
{
return var1 / var2;
}if(operator == '%')
{
return var1 % var2;
}
.
.
.
.
so onNow this thing alone taking worst case of 30 matches for each of the operator within the post fix, so if post fix has 10 operators, it is gonna take 30*10 = 300 matches (worst case). I'm not able to think of any proper solution for preventing this problem. Currently, I'm thinking of making 30 classes for each of the operator and every class implementing "iExpression" interface, with method signature "evaluate (int var1, int var2)" that will perform specific function during run time without going through 30 if-else statements. But again making 30 classes is weird solution?? Can anybody please help, I would really appreciate it. Regards, Shivam Kalra
-
Hi, I've a assignment where I have to write a program that can parse and evaluate certain numerical expression like
sin(30)*5*log10(300)/6^2%5
Well, I've already done my research through reading articles on code project, there are very good examples on this topic. So I've decided to use STACK based infix to post-fix conversion and finally evaluating the post-fix expression again using stack. Right Now, I've a class called "Expression" that stores each expression viz. *, /, %, sin, cos, log, tan..and many more. Let say you've following post fix expression
10 20 + 2 ^ sin 56 % 5 *
In simpler term, its infix expression is
(sin((10 + 20)^2) % 56) * 5
Now, during evaluating post fix expression, you encounter operators viz. *, /, ^, %, then you pop two elements from stack and perform this operation and finally you get result. I've like 30 of these mathematical operators, each time these operator occurs in post fix expression (operator is just a character in string), I perform search like
if(operator == '*')
{
return var1 * var2;
}if(operator == '*')
{
return var1 * var2;
}if(operator == '/')
{
return var1 / var2;
}if(operator == '%')
{
return var1 % var2;
}
.
.
.
.
so onNow this thing alone taking worst case of 30 matches for each of the operator within the post fix, so if post fix has 10 operators, it is gonna take 30*10 = 300 matches (worst case). I'm not able to think of any proper solution for preventing this problem. Currently, I'm thinking of making 30 classes for each of the operator and every class implementing "iExpression" interface, with method signature "evaluate (int var1, int var2)" that will perform specific function during run time without going through 30 if-else statements. But again making 30 classes is weird solution?? Can anybody please help, I would really appreciate it. Regards, Shivam Kalra
Seeing as this is an assignment, I'll try to give you a rough guide more so than a fully detailed answer, so the way I'm thinking is using a builder and a set of Operator types. Something like:
public interface IOperator
{
double Operate(double leftOperand, double rightOperand);
}public static class OperatorBuilder
{public IOperator BuildFromToken(string operatorToken) { switch (operatorToken) { case "\*": return new MultiplyOperator(); } }}
public class MultiplyOperator : IOperator
{
public double Operate(double leftOperand, double rightOperand)
{
return leftOperand * rightOperand;
}
}// example usage
public void Main(string[] args)
{// program is run like: // CalculatorExample.exe 5.0 6.0 \* var operator = OperatorBuilder.BuildFromToken(args\[2\]); Console.WriteLine( operator.Operate( double.Parse(args\[0\]), double.Parse(args\[1\]) ) .ToString() ); // should return 30.0}
Basically then your processing code doesn't give a damn what kind of operator it is, just so long as the OperatorBuilder returns the right one, it should call its Operate method with the operands in the post-fix sequence and get an answer. This way you are delegating three distinct responsibilities to different classes:
- OperatorBuilder - responsible for identifying tokens and returning the correct type of operator
- MultiplyOperator, AdditionOperator etc. - responsible for performing an operation on some operands
- Your processing code - the code you already have is doing the scanning part, which is separate (IMHO) from the semantic understanding of the text you are reading
I'm sure you can figure out how to expand this to your needs. This is just one idea off the top of my head, it's almost certainly not the best way to go about it, but I believe it should at least do the trick. PS Just proof-reading this... if you're lucky that example might even legitimately compile... ?
-
Hi, I've a assignment where I have to write a program that can parse and evaluate certain numerical expression like
sin(30)*5*log10(300)/6^2%5
Well, I've already done my research through reading articles on code project, there are very good examples on this topic. So I've decided to use STACK based infix to post-fix conversion and finally evaluating the post-fix expression again using stack. Right Now, I've a class called "Expression" that stores each expression viz. *, /, %, sin, cos, log, tan..and many more. Let say you've following post fix expression
10 20 + 2 ^ sin 56 % 5 *
In simpler term, its infix expression is
(sin((10 + 20)^2) % 56) * 5
Now, during evaluating post fix expression, you encounter operators viz. *, /, ^, %, then you pop two elements from stack and perform this operation and finally you get result. I've like 30 of these mathematical operators, each time these operator occurs in post fix expression (operator is just a character in string), I perform search like
if(operator == '*')
{
return var1 * var2;
}if(operator == '*')
{
return var1 * var2;
}if(operator == '/')
{
return var1 / var2;
}if(operator == '%')
{
return var1 % var2;
}
.
.
.
.
so onNow this thing alone taking worst case of 30 matches for each of the operator within the post fix, so if post fix has 10 operators, it is gonna take 30*10 = 300 matches (worst case). I'm not able to think of any proper solution for preventing this problem. Currently, I'm thinking of making 30 classes for each of the operator and every class implementing "iExpression" interface, with method signature "evaluate (int var1, int var2)" that will perform specific function during run time without going through 30 if-else statements. But again making 30 classes is weird solution?? Can anybody please help, I would really appreciate it. Regards, Shivam Kalra
GlobX's solution moves the problem (i.e. searching 30 operators each time) out of the way, but I don't think there's any way of actually avoiding it. However, you could use a Dictionary which you populate with all of the valid operators and their associated tokens, then use TryGetValue to return the IOperator instance to use. Of course, behind the scenes, the Dictionary still has to look through all the keys...
___________________________________________ .\\axxx (That's an 'M')
-
GlobX's solution moves the problem (i.e. searching 30 operators each time) out of the way, but I don't think there's any way of actually avoiding it. However, you could use a Dictionary which you populate with all of the valid operators and their associated tokens, then use TryGetValue to return the IOperator instance to use. Of course, behind the scenes, the Dictionary still has to look through all the keys...
___________________________________________ .\\axxx (That's an 'M')
-
Seeing as this is an assignment, I'll try to give you a rough guide more so than a fully detailed answer, so the way I'm thinking is using a builder and a set of Operator types. Something like:
public interface IOperator
{
double Operate(double leftOperand, double rightOperand);
}public static class OperatorBuilder
{public IOperator BuildFromToken(string operatorToken) { switch (operatorToken) { case "\*": return new MultiplyOperator(); } }}
public class MultiplyOperator : IOperator
{
public double Operate(double leftOperand, double rightOperand)
{
return leftOperand * rightOperand;
}
}// example usage
public void Main(string[] args)
{// program is run like: // CalculatorExample.exe 5.0 6.0 \* var operator = OperatorBuilder.BuildFromToken(args\[2\]); Console.WriteLine( operator.Operate( double.Parse(args\[0\]), double.Parse(args\[1\]) ) .ToString() ); // should return 30.0}
Basically then your processing code doesn't give a damn what kind of operator it is, just so long as the OperatorBuilder returns the right one, it should call its Operate method with the operands in the post-fix sequence and get an answer. This way you are delegating three distinct responsibilities to different classes:
- OperatorBuilder - responsible for identifying tokens and returning the correct type of operator
- MultiplyOperator, AdditionOperator etc. - responsible for performing an operation on some operands
- Your processing code - the code you already have is doing the scanning part, which is separate (IMHO) from the semantic understanding of the text you are reading
I'm sure you can figure out how to expand this to your needs. This is just one idea off the top of my head, it's almost certainly not the best way to go about it, but I believe it should at least do the trick. PS Just proof-reading this... if you're lucky that example might even legitimately compile... ?
Thank you. But, it is same as I suggested in my question. So if this the only good way, then it means I've to create 30 classes for each operator :((. Then use Operator Builder with hash table to perform operator search and finally get an answer. OMG too much work for 5% assignment. :mad:
-
Yes. Hash table look up is O(1) for less keys and I've only 30 operators. This is good idea. Thanks :)
-
GlobX's solution moves the problem (i.e. searching 30 operators each time) out of the way, but I don't think there's any way of actually avoiding it. However, you could use a Dictionary which you populate with all of the valid operators and their associated tokens, then use TryGetValue to return the IOperator instance to use. Of course, behind the scenes, the Dictionary still has to look through all the keys...
___________________________________________ .\\axxx (That's an 'M')
Indeed, making iOperator and then searching operator with hash table can bring worst case to O(1) complexity. Thanks :)
-
Thank you. But, it is same as I suggested in my question. So if this the only good way, then it means I've to create 30 classes for each operator :((. Then use Operator Builder with hash table to perform operator search and finally get an answer. OMG too much work for 5% assignment. :mad:
Sure, but as Maxx points out it's necessary complexity - just by the smell of it I don't think you can avoid the iterative approach. The program needs to know what "*" means and how to do it. It also needs to know what "+" means and how to do it, etc. ad infinitum. Besides, the operator class I gave you was what, 6 lines long? It won't take you long at all! Having said that, you could do something fancy and add attributes to the Operator classes that specify what token identifies that operation. You could then use reflection to, once again, loop over all the Operator classes in the Assembly and find the one with the matching token. This way you avoid a big set of if/else or switch/case statements, but it's going to be slower. Admittedly more fun, IMO, but definitely slower. In fact, as a practical solution I think that's crazy (but interesting). You could reduce the number of classes by changing IOperator into a single delegate:
// syntax is dubious
delegate double OperateDelegate(double left, double right);Then you could have a Dictionary/Hashtable mapping tokens ("*", "+", "sin" etc.) to delegates, which you could declare nice and compactly, like so:
var operatorLookup = new Dictionary();
operatorLookup.Add("*", ((left, right) => left * right));
operatorLoojup.Add("+", ((left, right) => left + right));// etc.
// OR you could go even MORE terse!var operatorLookup = new Dictionary
{
{ "*", ((left, right) => left * right) },
{ "+", ((left, right) => left + right) }
};// etc.
It's a trade-off of file-size vs. readability, which it is up to you as the developer to decide which one is important.
-
Seeing as this is an assignment, I'll try to give you a rough guide more so than a fully detailed answer, so the way I'm thinking is using a builder and a set of Operator types. Something like:
public interface IOperator
{
double Operate(double leftOperand, double rightOperand);
}public static class OperatorBuilder
{public IOperator BuildFromToken(string operatorToken) { switch (operatorToken) { case "\*": return new MultiplyOperator(); } }}
public class MultiplyOperator : IOperator
{
public double Operate(double leftOperand, double rightOperand)
{
return leftOperand * rightOperand;
}
}// example usage
public void Main(string[] args)
{// program is run like: // CalculatorExample.exe 5.0 6.0 \* var operator = OperatorBuilder.BuildFromToken(args\[2\]); Console.WriteLine( operator.Operate( double.Parse(args\[0\]), double.Parse(args\[1\]) ) .ToString() ); // should return 30.0}
Basically then your processing code doesn't give a damn what kind of operator it is, just so long as the OperatorBuilder returns the right one, it should call its Operate method with the operands in the post-fix sequence and get an answer. This way you are delegating three distinct responsibilities to different classes:
- OperatorBuilder - responsible for identifying tokens and returning the correct type of operator
- MultiplyOperator, AdditionOperator etc. - responsible for performing an operation on some operands
- Your processing code - the code you already have is doing the scanning part, which is separate (IMHO) from the semantic understanding of the text you are reading
I'm sure you can figure out how to expand this to your needs. This is just one idea off the top of my head, it's almost certainly not the best way to go about it, but I believe it should at least do the trick. PS Just proof-reading this... if you're lucky that example might even legitimately compile... ?
-
Sure, but as Maxx points out it's necessary complexity - just by the smell of it I don't think you can avoid the iterative approach. The program needs to know what "*" means and how to do it. It also needs to know what "+" means and how to do it, etc. ad infinitum. Besides, the operator class I gave you was what, 6 lines long? It won't take you long at all! Having said that, you could do something fancy and add attributes to the Operator classes that specify what token identifies that operation. You could then use reflection to, once again, loop over all the Operator classes in the Assembly and find the one with the matching token. This way you avoid a big set of if/else or switch/case statements, but it's going to be slower. Admittedly more fun, IMO, but definitely slower. In fact, as a practical solution I think that's crazy (but interesting). You could reduce the number of classes by changing IOperator into a single delegate:
// syntax is dubious
delegate double OperateDelegate(double left, double right);Then you could have a Dictionary/Hashtable mapping tokens ("*", "+", "sin" etc.) to delegates, which you could declare nice and compactly, like so:
var operatorLookup = new Dictionary();
operatorLookup.Add("*", ((left, right) => left * right));
operatorLoojup.Add("+", ((left, right) => left + right));// etc.
// OR you could go even MORE terse!var operatorLookup = new Dictionary
{
{ "*", ((left, right) => left * right) },
{ "+", ((left, right) => left + right) }
};// etc.
It's a trade-off of file-size vs. readability, which it is up to you as the developer to decide which one is important.
I think you are using anonymous method in C sharp, but unfortunately I'm using JAVA. I'm asking questions here because, in JAVA section nobody replies :laugh:. Anyways, I appreciate your help. Thank you.
-
I think you are using anonymous method in C sharp, but unfortunately I'm using JAVA. I'm asking questions here because, in JAVA section nobody replies :laugh:. Anyways, I appreciate your help. Thank you.
-
Hi, I've a assignment where I have to write a program that can parse and evaluate certain numerical expression like
sin(30)*5*log10(300)/6^2%5
Well, I've already done my research through reading articles on code project, there are very good examples on this topic. So I've decided to use STACK based infix to post-fix conversion and finally evaluating the post-fix expression again using stack. Right Now, I've a class called "Expression" that stores each expression viz. *, /, %, sin, cos, log, tan..and many more. Let say you've following post fix expression
10 20 + 2 ^ sin 56 % 5 *
In simpler term, its infix expression is
(sin((10 + 20)^2) % 56) * 5
Now, during evaluating post fix expression, you encounter operators viz. *, /, ^, %, then you pop two elements from stack and perform this operation and finally you get result. I've like 30 of these mathematical operators, each time these operator occurs in post fix expression (operator is just a character in string), I perform search like
if(operator == '*')
{
return var1 * var2;
}if(operator == '*')
{
return var1 * var2;
}if(operator == '/')
{
return var1 / var2;
}if(operator == '%')
{
return var1 % var2;
}
.
.
.
.
so onNow this thing alone taking worst case of 30 matches for each of the operator within the post fix, so if post fix has 10 operators, it is gonna take 30*10 = 300 matches (worst case). I'm not able to think of any proper solution for preventing this problem. Currently, I'm thinking of making 30 classes for each of the operator and every class implementing "iExpression" interface, with method signature "evaluate (int var1, int var2)" that will perform specific function during run time without going through 30 if-else statements. But again making 30 classes is weird solution?? Can anybody please help, I would really appreciate it. Regards, Shivam Kalra
-
Hi, I've a assignment where I have to write a program that can parse and evaluate certain numerical expression like
sin(30)*5*log10(300)/6^2%5
Well, I've already done my research through reading articles on code project, there are very good examples on this topic. So I've decided to use STACK based infix to post-fix conversion and finally evaluating the post-fix expression again using stack. Right Now, I've a class called "Expression" that stores each expression viz. *, /, %, sin, cos, log, tan..and many more. Let say you've following post fix expression
10 20 + 2 ^ sin 56 % 5 *
In simpler term, its infix expression is
(sin((10 + 20)^2) % 56) * 5
Now, during evaluating post fix expression, you encounter operators viz. *, /, ^, %, then you pop two elements from stack and perform this operation and finally you get result. I've like 30 of these mathematical operators, each time these operator occurs in post fix expression (operator is just a character in string), I perform search like
if(operator == '*')
{
return var1 * var2;
}if(operator == '*')
{
return var1 * var2;
}if(operator == '/')
{
return var1 / var2;
}if(operator == '%')
{
return var1 % var2;
}
.
.
.
.
so onNow this thing alone taking worst case of 30 matches for each of the operator within the post fix, so if post fix has 10 operators, it is gonna take 30*10 = 300 matches (worst case). I'm not able to think of any proper solution for preventing this problem. Currently, I'm thinking of making 30 classes for each of the operator and every class implementing "iExpression" interface, with method signature "evaluate (int var1, int var2)" that will perform specific function during run time without going through 30 if-else statements. But again making 30 classes is weird solution?? Can anybody please help, I would really appreciate it. Regards, Shivam Kalra
-
Hi, I've a assignment where I have to write a program that can parse and evaluate certain numerical expression like
sin(30)*5*log10(300)/6^2%5
Well, I've already done my research through reading articles on code project, there are very good examples on this topic. So I've decided to use STACK based infix to post-fix conversion and finally evaluating the post-fix expression again using stack. Right Now, I've a class called "Expression" that stores each expression viz. *, /, %, sin, cos, log, tan..and many more. Let say you've following post fix expression
10 20 + 2 ^ sin 56 % 5 *
In simpler term, its infix expression is
(sin((10 + 20)^2) % 56) * 5
Now, during evaluating post fix expression, you encounter operators viz. *, /, ^, %, then you pop two elements from stack and perform this operation and finally you get result. I've like 30 of these mathematical operators, each time these operator occurs in post fix expression (operator is just a character in string), I perform search like
if(operator == '*')
{
return var1 * var2;
}if(operator == '*')
{
return var1 * var2;
}if(operator == '/')
{
return var1 / var2;
}if(operator == '%')
{
return var1 % var2;
}
.
.
.
.
so onNow this thing alone taking worst case of 30 matches for each of the operator within the post fix, so if post fix has 10 operators, it is gonna take 30*10 = 300 matches (worst case). I'm not able to think of any proper solution for preventing this problem. Currently, I'm thinking of making 30 classes for each of the operator and every class implementing "iExpression" interface, with method signature "evaluate (int var1, int var2)" that will perform specific function during run time without going through 30 if-else statements. But again making 30 classes is weird solution?? Can anybody please help, I would really appreciate it. Regards, Shivam Kalra
I've used a much simpler approach to do this. The basic idea is you build a binary tree that represents your expression, where you have an interior node for each operator and its left and right sons are the operands. 1. Replace each token in your expression with a node that has left/right pointers, so it can be in a binary tree. Each number, operator, and parenthesis is a separate node. Initially the nodes are in a linear list, in the same order they appear in the expression. 2. We process the list, moving operand nodes to the left/right sons of operator nodes (or removing nodes) at each step, until we're left with a single node in the list: The root of the binary tree. 3. There are three operations: a) If you have a single node enclosed by parentheses, eliminate the parentheses: (N) => N b) Find the region most deeply nested in parentheses. Go through the nodes, moving the operands around the highest-precedence operators to the left/right sons: A + B * C + D => A + [* node with sons B and C] + D (Hard to draw a tree here...) c) Go through this region again, this time doing the same operation to the next-lower-precedence operators:
\[+ node\] / \\ \[+ node\] D / \\ A \[\* node\] / \\ B CWhen done, only the root [+ node] will remain in the list. To evaluate, call the Eval() method on the root. Eval returns the value of the node's operand, or for an operator, it returns the operator applied to the Eval() of its sons. It works, and it's way simpler than the standard approach.
-
Hi, I've a assignment where I have to write a program that can parse and evaluate certain numerical expression like
sin(30)*5*log10(300)/6^2%5
Well, I've already done my research through reading articles on code project, there are very good examples on this topic. So I've decided to use STACK based infix to post-fix conversion and finally evaluating the post-fix expression again using stack. Right Now, I've a class called "Expression" that stores each expression viz. *, /, %, sin, cos, log, tan..and many more. Let say you've following post fix expression
10 20 + 2 ^ sin 56 % 5 *
In simpler term, its infix expression is
(sin((10 + 20)^2) % 56) * 5
Now, during evaluating post fix expression, you encounter operators viz. *, /, ^, %, then you pop two elements from stack and perform this operation and finally you get result. I've like 30 of these mathematical operators, each time these operator occurs in post fix expression (operator is just a character in string), I perform search like
if(operator == '*')
{
return var1 * var2;
}if(operator == '*')
{
return var1 * var2;
}if(operator == '/')
{
return var1 / var2;
}if(operator == '%')
{
return var1 % var2;
}
.
.
.
.
so onNow this thing alone taking worst case of 30 matches for each of the operator within the post fix, so if post fix has 10 operators, it is gonna take 30*10 = 300 matches (worst case). I'm not able to think of any proper solution for preventing this problem. Currently, I'm thinking of making 30 classes for each of the operator and every class implementing "iExpression" interface, with method signature "evaluate (int var1, int var2)" that will perform specific function during run time without going through 30 if-else statements. But again making 30 classes is weird solution?? Can anybody please help, I would really appreciate it. Regards, Shivam Kalra
-
You can use CodeDom to create source code at runtime, compile and run it. If your numerical expressions can be evaluated in a programming language then I guess this might be the easiest way. This article[^] might give you some clues.
This will cheating. LOL. But nice article.
