Expression calculation in C#
Expression calculation in C#
2011-10-05 13:25?/yillc/article/details/6844931
Summary:
1. Improvement on the previous article: adding brackets
2. Changed the method of converting strings into infix expressions< /p>
1. Still knowledge of data structure:
1. Convert infix expression into postfix expression
Suppose the input of the algorithm is an infix expression infixExp (string), the output result is postfixExp, which is a value-preserving postfix expression.
Example: 23 + 34 * 45 / (5 + 6 + 7)? Converted to suffix: ?23? 34? 45? *? 5? 6? +? 7? +? /? +
2. Algorithm:
Scan infixExp from left to right, read each item and analyze its corresponding grammatical components:
1) When the input is The operand is output directly to postfixExp.
2) When the left bracket is entered, push it onto the stack.
3) When the input is a right parenthesis, first determine whether the stack is empty. If it is empty, the parentheses do not match; if not, the items in the stack are popped out in sequence until the first left parenthesis is encountered. Until the parentheses are encountered, the popped items will be output to postfixExp (the popped left parenthesis will not be output to postfixExp). If no left parenthesis is encountered, the parentheses will not match.
4) When the input is operator op (one of the four arithmetic operations + - */):
a) Loop, when (stack is not empty and the top of the stack is not a left parenthesis and (when the priority of the operator on the top of the stack is not lower than the priority of the input operator), repeat the operation: pop the element on the top of the stack and output it to postfixExp.
b) Push the input operator op onto the stack.
5) Finally, after all the symbol sequences of the infix expression infixExp are read in, there may be some items on the stack, which are grammatical components that have not been processed by the original push. The way to treat them is to pop them off the stack one by one and output them to the end of the postfix expression postfixExp.
2. For the evaluation of suffix, see the previous article
2. Convert the string into an infix expression and save it in Q1
If there is no A good algorithm comes to mind. That is to split the string, save the value into the split array resSplit, and then traverse the original string res to find the operator.
Looking forward to finding better algorithms.
[csharp]?view plaincopy
?//Response code for button "="?
protected?void?ButtonEqual_Click(object?sender ,?EventArgs?e)?
{?
int?si=0;?
int?s=1;//when s=0: The previous element is a number.
When s=1, the previous one is the symbol?
String?res?=?TextBoxResult.Text;?
char[]?str?=? TextBoxResult.Text.ToCharArray();?
string[]?resSplit?=?res.Split(new?char[]?{?'+',?'-',?'*', ?'/','(',')'?});?
try?
{?
for?(int?i?= ?0;?i?
{?
node?tmp?=?new?node();//Temporary node?< /p>
if?((str[i]==46||(?str[i]?-?48?<=?9?&&?0?<=?str[i]?-?48 )?)&&?s?==?1)//The newly added element is a numerical value?
{?
tmp.sign?=?false;?
while?(true?)?
{?
if?(resSplit[si]?!=?"")?
{?
tmp.num?=?Convert.ToDouble(resSplit[si]);?
break;?
}?
else?si++;?
}?
Q1.Enqueue(tmp);?
Label1.Text?=?Label1.Text?+?tmp. num;//Test?
s?=?0;?
si++;
}?
else?if?( (str[i]==46||(?str[i]?-?48?<=?9?&&?0?<=?str[i]?-?48))?&&?s?== ?0)//The newly added element is a number, but the previous element is also?
{?
continue;?
}?
< p>else?{?
tmp.sign?=?true;?
tmp.symbol?=?str[i];?
if?(tmp.symbol?==?'*'?||?tmp.symbol?==?'/')?tmp.priority?=?2;?
else?if?(tmp.symbol?==?'+'?||?tmp.symbol?==?'-')?tmp.priority?=?1;?
s?= ?1;?
Q1.Enqueue(tmp);?
Label1.Text?=?Label1.Text?+?tmp.symbol;//Test?
}?
}?
change();?
double?r?=?calculate();?
if(err==false)?Label1.Text?=?Label1.Text?+?"="?+?r+?"
elseLabel1.Text?= ?Label1.Text?+"error!
}?
catch?(Exception?ew)?
{?
Label1.Text?=?Label1.Text?+"error!
}?
}?
?Three infix-suffix
[csharp]?view plaincopy
?public?void?change()//2)?Convert infix expression to postfix expression;?
{?
while?(Q1.Count?!= ?0)?
{?
if?(Q1.Peek().sign?==?false)//It is a number, put it in the queue?
< p>{?Q2.Enqueue(Q1.Peek());?
}?
else?
{?
if?(Q1.Peek().symbol?==?'(')//When the left bracket is entered, push it onto the stack. ?
Sc.Push(Q1.Peek());?
else?if?(Q1.Peek().symbol?==?')')//When The input is the right bracket, ?
{?
if?(Sc.Count()?==?0)?
{?
err?=?true;?
break;?
}?
else?
{?
while?(Sc.Peek().symbol?=?'(')?
{?
Q2.Enqueue(Sc.Peek()) ;?
Sc.Pop();?
if?(Sc.Count()?==?0)?
{?
err?=?true;?
break;?
}?
}?
if?(Sc .Count()?=?0)?Sc.Pop();?
}?
}
else?
{?
while?(Sc.Count()!=?0?&&?Q1.Peek().symbol?=?'('?&&?Q1.Peek().priority? <=?Sc.Peek().priority)?
{?
Q2.Enqueue(Sc.Peek());?
Sc.Pop ();?
}?
Sc.Push(Q1.Peek());?
}
}?< /p>
Q1.Dequeue();?
}?
while?(Sc.Count()?!=?0)?
{?
if?(Sc.Peek().symbol?==?'(')?
{?
err?=?true ;?
break;?
}?
Q2.Enqueue(Sc.Peek());?
Sc.Pop ();?
}
?
}
?Four? suffix solution?
< p>[csharp]?view plaincopypublicdouble?calculate()?
{?
Stack
double?num1?=?0;?
double?num2?=?0;?
node?tmp?= ?new?node();?
while?(Q2.Count?=?0)?
{?
if?(Q2.Peek ().sign?==?false)?
{?
stmp.Push(Q2.Peek());?
}?
else?if?(Q2.Peek().sign?==?true)?
{?
num2?=?stmp.Peek(). num;?
stmp.Pop();?
num1?=?stmp.Peek().num;?
stmp.Pop(); ?
if?(Q2.Peek().symbol?==?'+')?
{?
tmp.num?=?num1 ?+?num2;?
tmp.priority?=?1;?
tmp.sign?=?false;?
}?
else?if?(Q2.Peek().symbol?==?'-')?
{?
tmp.num?=?num1?- ?num2;?
tmp.priority?=?1;?
tmp.sign?=?false;?
}?
< p>else?if?(Q2.Peek().symbol?==?'*')?{?
tmp.num?=?num1?*?num2 ;?
tmp.priority?=?2;?
tmp.sign?=?false;?
}?
else?if?(Q2.Peek().symbol?==?'/')?
{?
tmp.num?=?num1?/?num2;?
tmp.priority?=?2;?
tmp.sign?=?false;?
}
stmp.Push (tmp);?
}?
Q2.Dequeue();?
}?
if?(stmp.Count ()?=?1)?err?=?true;?
return?stmp.Peek().num;?
}?
5. Shortcomings:
1 I wrote a little casually, and the code is still very irregular
2 When an error occurs, all errors are reported, error!, without subdivisions
3 It is limited to double type and cannot achieve high precision
4 Negative numbers are not supported, such as -6. An error will occur during calculation. It needs to be written as: (0-6)