算术表达式求值是一个经典的问题,很多学习编程的人都对此不陌生.本来我并不想写一个算术表达式求值的算法.在网上我看到了一篇文章,名叫<快速精确的对数学表达式求值>(http://www-128.ibm.com/developerworks/cn/java/j-w3eva/).才有兴趣着一个玩玩.写来写去,觉得真得很经典.所以把我写的代码拿出来让大家看看吧.因为时间较紧.所以变量名没有做得很规范.
w3eavl是用JAVA写得,我用C#把它重写了一下.基本上能用,只是三角函数/反三角函数/双曲线函数计算不太正常.谁对算术表达式求值感兴趣可以和我联系.原程序截图:
我用C#重写的(实其是用他的代码改为C#语法.)
谁想要W3Eval的JAVA代码.和我改写的C#代码.可以和我联系.下面要讲的这个逆波兰式求值算法的代码也可以向我索取.请不要在商业中使用我的代码.如果需要使用.请通知我.
我是的算法核心是逆波兰式.还有就是w3eval这个算术表达式求值算法很不错.但有一种表达式它会报错.我想这是一个BUG:w3eavl不能计算"-(3+5)"的值.或者类似的计算式.
在生成逆波兰式时,负号前缀是一个很大的麻烦.因为它和减号共用一个符号.我的做法是将负号前缀做一个预处理.负号在我这里做为单目运算符求反.并将其替换还为"!".
为了可以扩充新的各种级别的运算符我为运算符的优先级做了一个Power()函数.如果出现了新的优先级级别.只要在这里调整就可以了.
后缀式求值本没有什么好说的.只是.单目运算和双目运算还行三目运算对于它来说就不太好玩了.幸亏三目运算不多.不然,那都是事儿.
using System;
namespace XIYV.Compute
{
///
/// SimpleRPN 的摘要说明。
///
public sealed class SimpleRPN
{
private SimpleRPN(){}
///
/// Reverse Polish Notation
/// 算术逆波兰表达式.生成.
///
///
///
private static string BuildingRPN(string s)
{
System.Text.StringBuilder sb=new System.Text.StringBuilder(s);
System.Collections.Stack sk=new System.Collections.Stack();
System.Text.StringBuilder re=new System.Text.StringBuilder();
char c=' ';
//sb.Replace(" ","");//一开始,我只去掉了空格.后来我不想不支持函数和常量能滤掉的全OUT掉.
for(int i=0;i { c=sb[i]; if(char.IsDigit(c))//数字当然要了. re.Append(c); //if(char.IsWhiteSpace(c)||char.IsLetter(c))//如果是空白,那么不要.现在字母也不要. //continue; switch(c)//如果是其它字符...列出的要,没有列出的不要. { case '+': case '-': case '*': case '/': case '%': case '^': case '!': case '(': case ')': case '.': re.Append(c); break; default: continue; } } sb=new System.Text.StringBuilder(re.ToString()); #region 对负号进行预转义处理.负号变单目运算符求反. for(int i=0;i if(sb[i]=='-'&&(i==0||sb[i-1]=='(')) sb[i]='!';//字符转义. #endregion #region 将中缀表达式变为后缀表达式. re=new System.Text.StringBuilder(); for(int i=0;i { if(char.IsDigit(sb[i])||sb[i]=='.')//如果是数值. { re.Append(sb[i]);//加入后缀式 } else if(sb[i]=='+' ||sb[i]=='-' ||sb[i]=='*' ||sb[i]=='/' ||sb[i]=='%' ||sb[i]=='^' ||sb[i]=='!')//. { #region 运算符处理 while (sk.Count>0) //栈不为空时 { c = (char)sk.Pop(); //将栈中的操作符弹出. if (c == '(') //如果发现左括号.停. { sk.Push(c); //将弹出的左括号压回.因为还有右括号要和它匹配. break; //中断. } else { if(Power(c) { sk.Push(c); break; } else { re.Append(' '); re.Append(c); } //如果不是左括号,那么将操作符加入后缀式中. } } sk.Push(sb[i]); //把新操作符入栈. re.Append(' '); #endregion } else if(sb[i]=='(')//基本优先级提升 { sk.Push('('); re.Append(' '); } else if(sb[i]==')')//基本优先级下调 { while (sk.Count>0) //栈不为空时 { c = (char)sk.Pop(); //pop Operator if (c != '(') { re.Append(' '); re.Append(c);//加入空格主要是为了防止不相干的数据相临产生解析错误. re.Append(' '); } else break; } } else re.Append(sb[i]); } while(sk.Count>0)//这是最后一个弹栈啦. { re.Append(' '); re.Append(sk.Pop()); } #endregion re.Append(' '); return FormatSpace(re.ToString());//在这里进行一次表达式格式化.这里就是后缀式了. } /// /// 算术逆波兰表达式计算. /// /// /// public static string ComputeRPN(string s) { string S=BuildingRPN(s); string tmp=""; System.Collections.Stack sk=new System.Collections.Stack(); char c=' '; System.Text.StringBuilder Operand=new System.Text.StringBuilder(); double x,y; for(int i=0;i { c=S[i]; if(char.IsDigit(c)||c=='.') {//数据值收集. Operand.Append(c); } else if(c==' '&&Operand.Length>0) { #region 运算数转换 try { tmp=Operand.ToString(); if(tmp.StartsWith("-"))//负数的转换一定要小心...它不被直接支持. {//现在我的算法里这个分支可能永远不会被执行. sk.Push(-((double)Convert.ToDouble(tmp.Substring(1,tmp.Length-1)))); } else { sk.Push(Convert.ToDouble(tmp)); } } catch { return "发现异常数据值."; } Operand=new System.Text.StringBuilder(); #endregion } else if(c=='+'//运算符处理.双目运算处理. ||c=='-' ||c=='*' ||c=='/' ||c=='%' ||c=='^') { #region 双目运算 if(sk.Count>0)/*如果输入的表达式根本没有包含运算符.或是根本就是空串.这里的逻辑就有意义了.*/ { y=(double)sk.Pop(); } else { sk.Push(0); break; } if(sk.Count>0) x=(double)sk.Pop(); else { sk.Push(y); break; } switch(c) { case '+': sk.Push(x+y); break; case '-': sk.Push(x-y); break; case '*': sk.Push(x*y); break; case '/': sk.Push(x/y); break; case '%': sk.Push(x%y); break; case '^': // if(x>0) // {我原本还想,如果被计算的数是负数,又要开真分数次方时如何处理的问题.后来我想还是算了吧. sk.Push(System.Math.Pow(x,y)); // } // else // { // double t=y; // string ts=""; // t=1/(2*t); // ts=t.ToString(); // if(ts.ToUpper().LastIndexOf('E')>0) // { // ; // } // } break; } #endregion } else if(c=='!')//单目取反.) { sk.Push(-((double)sk.Pop())); } } if(sk.Count>1) return "运算没有完成."; if(sk.Count==0) return "结果丢失.."; return sk.Pop().ToString(); } /// /// 优先级别测试函数. /// /// /// private static int Power(char opr) { switch(opr) { case '+': case '-': return 1; case '*': case '/': return 2; case '%': case '^': case '!': return 3; default: return 0; } } /// /// 规范化逆波兰表达式. /// /// /// private static string FormatSpace(string s) { System.Text.StringBuilder ret=new System.Text.StringBuilder(); for(int i=0;i { if(!(s.Length>i+1&&s[i]==' '&&s[i+1]==' ')) ret.Append(s[i]); else ret.Append(s[i]); } return ret.ToString();//.Replace('!','-'); } } /*这里给出的测试用例虽然不多.但如都能成功计算也不容易. (6+9-8+5-8)*(2+5+8)/7+5 (1+2+3+4+5+6+7+8+9)*(1+2+3+4+5+6+7+8+9)/(9+8+7+6)*3-2-2+5/7-3 (-3+4+9)*(-3)*7/(-5*2) -(6+9-8+5-8)*(2+5+8) 1+2+3+4+5+6+7+8+9 1*2*3*4*5*6*7*8*9 1-2-3-4-5-6-7-8-9 1/2/3/4/5/6/7/8/9 (6+9-8+5-8)*(2+5+8) */ }