面试题，高手接招，有分哦

Question

这是我面试时的一道题，算是题量比较大的：请用你较熟悉的一种编程语言实现 数学表达式的计算
输入：数学表达式字符串，比如5.6+(sin(7-5)ln45)/9.8 (可计算的表达式复杂程度的最低
      要求：至少能计算 由浮点数与 + - * / sin cos ln () !(阶乘） 混合组成的数学表达式)
输出：表达式的计算结果 或 表达式的错误信息（如果表达式存在错误的话，比如
      5.6+sin(cosg7.3)-5/0 出现了未定义字符g以及除数为0 )请大家一起来show一下技术哈，在实现计算的基础上请尽量减少对时间空间的消耗以及在清晰明了的
基础上尽量缩短代码

Answer 1

本人原创，转贴请注明出处
有些结构体定义在其它类库中，此处不贴了。
本类库暂只实现了+-*/ 外带任意多的括号的计算，其实sin、cos之类也只是多一些工作量，无技术难度。执行速度并未做过详细测试using System;
using System.Collections;namespace CrobMathExpress
{
/// <summary>
/// 数学表达式解析计算
/// </summary>
public class MathExpress
{
public struct TAG_MIDMATH
{
public string szExp;
public double dItem; //运算结果值
public char cItemOperator; //后续运算符
public bool bHasResult;
} /// <summary>
/// 变量对应值结构
/// </summary>
public struct TAG_VARIANTCALC
{
public string szVariant;
public string szObjectID; //变量值查询类型
public double dValue;
} private string m_szCharset = " _abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ01234567890.()+-*/";
private TAG_RISKFUNCTION_PARAMS m_tParams = new TAG_RISKFUNCTION_PARAMS();
private ArrayList m_arVariant = new ArrayList(); private TAG_RISK_VARIANT[] m_arExistsVariant = null; //变量表

public MathExpress(TAG_RISK_VARIANT[] arVariant)
{
m_arExistsVariant = arVariant;
} #region 数学表达式解析 public void Prepare()
{
m_arVariant.Clear();
} /// <summary>
///  解析表达式
/// </summary>
/// <param name="iszExpress"></param>
/// <param name="bTest">仅测试表达式是否正确</param>
/// <param name="oValue">计算结果值</param>
/// <param name="oszMsg"></param>
/// <returns></returns>
public bool ExpressAnalyse(string iszExpress, bool bTest, ref double oValue, ref string oszMsg)
{
iszExpress = iszExpress.ToUpper();
if(!CheckExpressCharset(iszExpress))
{
oszMsg = "表达式包含非法字符";
return false;
}
if(iszExpress.Length <= 0)
{
oszMsg = "表达式不能为空";
return false;
} ArrayList arItem = new ArrayList();
if(IsSimpleExpress(iszExpress))
{
//简单表达式，只有加减乘除运算，计算出其值
if(!ParseSimpleExpress_to_arr(iszExpress, ref arItem, ref oszMsg))return false; //表达式错误

//根据arItem计算出值
if(!SimpleExpress_calculator(arItem, bTest, ref oValue, ref oszMsg))return false; return true;
} bool bFirstBrcket = true;
int i = 0;
int itmp = 0;
int iLastBrcketRight = 0;
for(i=0; i<iszExpress.Length; i++)
{
int iBracketRight = 0;
if(iszExpress[i] == '(')
{
//找到第一个括号之前的表达式要放入arItem
if(bFirstBrcket)
{
if(!ParseSimpleExpress_to_arr(iszExpress.Substring(0, i), ref arItem, ref oszMsg))
{
return false; //表达式错误
}
bFirstBrcket = false;
} //找出右括号，并递归计算其中表达式值
if(!MachingBracket(iszExpress, i, ref iBracketRight))
{
//表达式错误
oszMsg = String.Format("表达式括号不匹配[位置{0}]", i);
return false;
}

string szNewExpress = iszExpress.Substring(i+1, iBracketRight - i - 1); double dtmp = 0.000;
if(!ExpressAnalyse(szNewExpress, bTest, ref dtmp, ref oszMsg))return false; //表达式错误 //缓存该单元计算的结果值
TAG_MIDMATH tItem = new TAG_MIDMATH();
tItem.dItem = dtmp;
tItem.bHasResult = true;
tItem.szExp = szNewExpress;
tItem.cItemOperator = 'N';
//查找后续符号
itmp = iBracketRight;
bool bFindOperator = false;
for(itmp = iBracketRight; itmp<iszExpress.Length; itmp++)
{
switch(iszExpress[itmp])
{
case '+':
case '-':
case '*':
case '/':
tItem.cItemOperator = iszExpress[itmp];
bFindOperator = true;
break;
} if(!bFindOperator)if(iszExpress[itmp] != ' ' && iszExpress[itmp] != ')' && iszExpress[itmp] != '(')return false; //表达式错误
if(tItem.cItemOperator != 'N')break; //找到后续符号
}
arItem.Add(tItem); i = itmp;
iLastBrcketRight = itmp; //已经加上了后续符号的位置
} } if((iLastBrcketRight + 1 < iszExpress.Length))
{
//找到最后一个括号后面的表达式
if(!ParseSimpleExpress_to_arr(iszExpress.Substring(iLastBrcketRight + 1, iszExpress.Length - iLastBrcketRight - 1), ref arItem, ref oszMsg))return false; //表达式错误
} //根据arItem中的内容计算出值
if(!SimpleExpress_calculator(arItem, bTest, ref oValue, ref oszMsg))return false;
return true;
}
/// <summary>
/// 计算一般表达式数组的值
/// </summary>
/// <param name="arItem"></param>
/// <returns></returns>
public bool SimpleExpress_calculator(ArrayList arItem, bool bTest, ref double odValue, ref string oszMsg)
{
odValue = 0.000;
int i = 0;
ArrayList arTmp = new ArrayList();
//先计算出其中的乘除法表达式的值
for(i = 0; i<arItem.Count; i++)
{
TAG_MIDMATH tItem = (TAG_MIDMATH)arItem[i];
switch(tItem.cItemOperator)
{
case '+':
case '-':
//tItem.bHasResult = false;
arTmp.Add(tItem);
break;
case '*':
case '/':
{
double dResultTmp = 0.000;
if(!GetVariantResult(tItem, bTest, ref dResultTmp, ref oszMsg))return false; //将乘除法计算为单独的值结构
for(int itmp = i; itmp < arItem.Count; itmp++)
{
if(itmp + 1 >= arItem.Count)return false; //表达式错误
TAG_MIDMATH t1 = (TAG_MIDMATH)arItem[itmp];
TAG_MIDMATH t2 = (TAG_MIDMATH)arItem[itmp + 1];
double dValue2 = 0.000; //temp  临时取值，以后替换为变量取值
if(!GetVariantResult(t2, bTest, ref dValue2, ref oszMsg))return false; if(t1.cItemOperator == '*')
{
dResultTmp = dResultTmp * dValue2;
}
else if(t1.cItemOperator == '/')
{
dResultTmp = dResultTmp / dValue2;
} if(t2.cItemOperator != '*' && t2.cItemOperator != '/')
{
//一段乘除法计算完成，入值
TAG_MIDMATH tmp = new TAG_MIDMATH();
tmp.dItem = dResultTmp;
tmp.cItemOperator = t2.cItemOperator;
tmp.bHasResult = true;
arTmp.Add(tmp);
i = itmp + 1;
break;
}
}
}
break;
case 'N': //表达式最后一个值，没有运算符
//tItem.bHasResult = false;
arTmp.Add(tItem);
break;
}
} if(arTmp.Count <= 0)
{
odValue = 0.000;
}
else
{
TAG_MIDMATH ttmp = (TAG_MIDMATH)arTmp[0];
if(!GetVariantResult(ttmp, bTest, ref odValue, ref oszMsg))return false; for(i = 0; i<arTmp.Count; i++)
{
TAG_MIDMATH t1 = (TAG_MIDMATH)arTmp[i];
if(i + 1 < arTmp.Count)
{
TAG_MIDMATH t2 = (TAG_MIDMATH)arTmp[i + 1];
double dValue = 0.000;
if(!GetVariantResult(t2, bTest, ref dValue, ref oszMsg))return false; switch(t1.cItemOperator)
{
case '+':
odValue += dValue;
break;
case '-':
odValue -= dValue;
break;
case 'N':
break;
}
}
}
} return true;
}

Answer 2

/// <summary>
/// 解析一般简单表达式到数组
/// </summary>
/// <param name="iszExpress"></param>
/// <param name="oArr"></param>
/// <returns></returns>
public bool ParseSimpleExpress_to_arr(string iszExpress, ref ArrayList oArr, ref string oszMsg)
{
iszExpress = iszExpress.Trim();
int i = 0;
string stmp = "";
for(i = 0; i < iszExpress.Length; i++)
{
switch(iszExpress[i])
{
case ')':
case '(':
oszMsg = "表达式括号不匹配";
return false; //简单表达式不应有括号
break;
case '+':
case '-':
case '*':
case '/':
{
stmp = stmp.Trim();
if(stmp.Length <= 0)
{
oszMsg = String.Format("运算符 \"{0}\" 前没有找到运算单元", iszExpress[i]);
return false; //表达式错误
}
TAG_MIDMATH tItem = new TAG_MIDMATH();
tItem.szExp = stmp;
tItem.dItem = 0.00; //变量
tItem.cItemOperator = iszExpress[i];
oArr.Add(tItem); stmp = "";
}
break;
default:
stmp += String.Format("{0}", iszExpress[i]);
break;
} } stmp = stmp.Trim();
if(stmp.Length > 0)
{
TAG_MIDMATH tItem = new TAG_MIDMATH();
tItem.szExp = stmp;
tItem.dItem = 0.00; //变量
tItem.cItemOperator = 'N';
oArr.Add(tItem);
}
return true;
} /// <summary>
/// 判断是否是最简单表达式
/// </summary>
/// <param name="m_iszExpress"></param>
/// <returns></returns>
public bool IsSimpleExpress(string m_iszExpress)
{
int i = 0;
for(i = 0; i<m_iszExpress.Length; i++)
{
switch(m_iszExpress[i])
{
case '(':
case ')':
return false;
break;
}
}
return true;
}

Answer 3

/// <summary>
/// 匹配括号，找到指定位置的括号所对应的反括号的位置
/// </summary>
public bool MachingBracket(string m_iszExpress, int iStart, ref int oEnd)
{
if(iStart >= m_iszExpress.Length)return false; //越界 char cNow = m_iszExpress[iStart];
if(cNow != '(' && cNow != ')')return false; //当前位置不是括号字符
int i = 0;
int a1 = 0;
int a2 = 0; oEnd = -1;
for(i = iStart; i<m_iszExpress.Length; i++)
{
if(m_iszExpress[i] == cNow)
{
a1 ++;
}
else
{
switch(cNow)
{
case '(':
if(m_iszExpress[i] == ')')
a2++;
break;
case ')':
if(m_iszExpress[i] == '(')
a2++;
break;
}
} if(a1 == a2)
{
//找到了对应位置的反括号
oEnd = i;
break;
}
} return oEnd >= 0;
} /// <summary>
/// 检查表达式中是否有非法字符
/// </summary>
/// <param name="iszExpress"></param>
/// <returns></returns>
private bool CheckExpressCharset(string iszExpress)
{
for(int i = 0; i<iszExpress.Length; i++)
{
if(iszExpress[i] == ' ')continue;
if(!InString(m_szCharset, iszExpress[i]))
{
return false;
}
}
return true;
} public  static bool InString(string isz, char ic)
{
for(int i=0; i<isz.Length; i++)
{
if(ic == isz[i])return true;
}
return false;
}
#endregion #region 获得表达式变量值
/// <summary>
/// 获得表达式单元的值
/// </summary>
/// <param name="tItem"></param>
/// <param name="dValue"></param>
/// <returns></returns>
public bool GetVariantResult(TAG_MIDMATH tItem, bool bTest, ref double dValue, ref string oszMsg)
{
dValue = 0.0000;
if(tItem.bHasResult)
{
//已经有值，不用再获得
dValue = tItem.dItem;
}
else
{
//需要计算的变量或数值到dItem
if(IsDouble(tItem.szExp))
{
dValue = Convert.ToDouble(tItem.szExp);
}
else
{
//是表达式变量，需要判断取值
dValue = 1;
if(bTest)
{
dValue = 1;
//检查变量是否存在
if(m_arExistsVariant != null)
{
bool bFind = false;
string szObjectID = "";
foreach(TAG_RISK_VARIANT tin in m_arExistsVariant)
{
if(tin.PARENTID < 0)continue;
if(tin.EXPRESSION.ToUpper().Trim().Equals(tItem.szExp.ToUpper().Trim()))
{
bFind = true;
szObjectID = tin.OBJECTID;
break;
}
} if(!bFind)
{
oszMsg = String.Format("无效的变量名{0}", tItem.szExp);
return false;
}
else
{
//放入到临时数组，为计算变量值做准备
dValue = 1;
TAG_VARIANTCALC tVariant = new TAG_VARIANTCALC();
tVariant.szVariant = tItem.szExp.Trim();
tVariant.szObjectID = szObjectID;
tVariant.dValue = 0.0000; bool bFindVariant = false;
foreach(TAG_VARIANTCALC tin in m_arVariant)
{
if(tin.szVariant.Equals(tItem.szExp.Trim()))
{
bFindVariant = true;
break;
}
}
if(!bFindVariant)
{
m_arVariant.Add(tVariant);
}
}
}
else
{
oszMsg = String.Format("无效的变量名{0}", tItem.szExp);
return false;
}
}
else
{
//从arVariant取得变量值
bool bFind = false;
for(int i = 0; i<m_arVariant.Count; i++)
{
TAG_VARIANTCALC tVariant = (TAG_VARIANTCALC)m_arVariant[i];
if(tVariant.szVariant.Trim().ToUpper().Equals(tItem.szExp.Trim().ToUpper()))
{
dValue = tVariant.dValue;
bFind = true;
break;
}
}
if(!bFind)
{
oszMsg = String.Format("无效的变量名{0}", tItem.szExp);
return false;
} }
}
}
return true;
} /// <summary>
/// 计算arVariant中的变量的值
/// </summary>
public bool CalculatorVariant(IEntryModule iInfoQuery)
{
ArrayList arOther = new ArrayList();
for(int i = 0; i<m_arVariant.Count; i++)
{
TAG_VARIANTCALC tVariant = (TAG_VARIANTCALC)m_arVariant[i];
switch(tVariant.szVariant.Trim().ToUpper())
{
case "PREQTY": //预先委托数量
tVariant.dValue = m_tParams.iPreQyt;
m_arVariant[i] = tVariant;
break;
case "ENTRUSTQTY":
tVariant.dValue = m_tParams.iEntrustQty;
m_arVariant[i] = tVariant;
break;
case "ENTRUSTMONEY":
tVariant.dValue = m_tParams.dEntrustMoney;
m_arVariant[i] = tVariant;
break;
case "ENTRUSTPRICE":
tVariant.dValue = m_tParams.dEntrustPrice;
m_arVariant[i] = tVariant;
break; //需要从数据库查询值的变量
case "MAINHOLDQTY":
case "SUBHOLDQTY":
arOther.Add(tVariant);
break;
default:
arOther.Add(tVariant);
break;
}
} if(arOther.Count > 0)
{
if(iInfoQuery == null)return false; TAG_RISKVALUE[] arV2 = new TAG_RISKVALUE[arOther.Count];
for(int i = 0; i<arOther.Count; i++)
{
TAG_VARIANTCALC tVar = (TAG_VARIANTCALC)arOther[i]; if(tVar.szObjectID == "-1" || tVar.szObjectID.Length <= 0)
{
//没有数据查询ID
return false;
}

arV2[i].szObjectType = tVar.szObjectID;
arV2[i].szCseq = m_tParams.szCseq;
arV2[i].szSubCseq = m_tParams.szSubcseq;
arV2[i].szStock = m_tParams.szStockCode;
arV2[i].szMarket = m_tParams.szSeid; arV2[i].dPrice = m_tParams.dPrice;
} TAG_RETURNRISKVALUE[] arReturnVal = null; //m_base.Risk_query_variant(arV2, ref arReturnVal); //查询数据库
//************************************************************
//****** 从数据库查询变量值
iTFParam paramout = null;
iTFParam paramin = new iTFParam(2);
paramin.objParam[0] = 6126;
paramin.objParam[1] = arV2; int nRet = -1;
try
{
nRet = iInfoQuery.FunctionExecute(paramin, ref paramout);
}
catch
{
return false;
} if (nRet!=0)
{
return false;
}
if(paramout.objParam != null)
{
try
{
arReturnVal= (TAG_RETURNRISKVALUE[])paramout.objParam[0];
}
catch
{
return false;
}
}
//************************************************************ if(arReturnVal == null)return false;
if(arReturnVal.Length != arV2.Length)return false; //把变量值放回到arVariant for(int i = 0; i<arOther.Count; i++)
{
TAG_VARIANTCALC tVar = (TAG_VARIANTCALC)arOther[i];
if(!IsDouble(arReturnVal[i].szReturnValue.Trim()))return false; for(int i2 = 0; i2<m_arVariant.Count; i2++)
{
TAG_VARIANTCALC t1 = (TAG_VARIANTCALC)m_arVariant[i2];
if(t1.szVariant.Equals(tVar.szVariant))
{
t1.dValue = Convert.ToDouble(arReturnVal[i].szReturnValue.Trim());
m_arVariant[i] = t1;
}
}
}
} return true;
} /// <summary>
/// 判断是不是数值类型的字串
/// </summary>
/// <param name="szExp"></param>
/// <returns></returns>
public bool IsDouble(string szExp)
{
try
{
double d1 = Convert.ToDouble(szExp);
}
catch
{
return false;
}
return true;
} public bool SetParams(TAG_RISKFUNCTION_PARAMS itParam)
{
m_tParams = itParam;
return true;
} #endregion
}
}