/// <summary> /// 中缀表达式到逆波兰表达式的转换及求值 /// </summary> public class RpnExpression { #region 定义属性 int Top = -1; #endregion /// <summary> /// 检查中缀表达式是否合法 /// </summary> /// <param name="exp"></param> /// <returns></returns> public bool IsRight(string exp) { string pMatch = @"\([^\(^\)]+\)";//匹配最“内”层括号及表达式 string numberMatch = @"\d+(\.\d+)?";//匹配数字 string exMatch = @"^0([-+*/]0)*$";//匹配无括号的、用0替换所有的数字后的表达式 exp = Regex.Replace(exp, numberMatch, "0");//为简化检测，用0替换所有的数字 while (Regex.IsMatch(exp, pMatch)) { foreach (Match match in Regex.Matches(exp, pMatch)) { string tmp = match.Value; tmp = tmp.Substring(1, tmp.Length - 2);//去掉 "("和 ")" if (!Regex.IsMatch(tmp, exMatch)) return false; } exp = Regex.Replace(exp, pMatch, "0");//将最内层的括号及括号内表达式直接用一个0代替 } return Regex.IsMatch(exp, exMatch); } #region 生成逆波兰表达式 /// <summary> /// 获取逆波兰表达式 /// </summary> /// <param name="exp"></param> /// <returns></returns> public string RpnExp(string exp) { string S = ""; //后缀 char[] Operators = new char[exp.Length]; for (int i = 0; i < exp.Length; i++) { char C = exp[i]; switch (C) { case ' ': //忽略空格 break; case '+': //操作符 case '-': while (Top >= 0) //栈不为空时 { char c = Operators[Top--]; //pop Operator if (c == '(') { Operators[++Top] = c; //push Operator break; } else { S = S + c; } } Operators[++Top] = C; //push Operator S += " "; break; case '*': //忽略空格 case '/': while (Top >= 0) //栈不为空时 { char c = Operators[Top--]; //pop Operator if (c == '(') { Operators[++Top] = c; //push Operator break; } else { if (c == '+' || c == '-') { Operators[++Top] = c; //push Operator break; } else { S = S + c; } } } Operators[++Top] = C; //push Operator S += " "; break; case '(': Operators[++Top] = C; S += " "; break; case ')': while (Top >= 0) //栈不为空时 { char c = Operators[Top--]; //pop Operator if (c == '(') { break; } else { S = S + c; } } S += " "; break; default: S = S + C; break; } } while (Top >= 0) { S = S + Operators[Top--]; //pop Operator } return S; } #endregion #region 取逆波兰表达式的值 /// <summary> /// 获取逆波兰表达式的值 /// </summary> /// <param name="rpnExp"></param> /// <returns></returns> public double GetValueByRpn(string rpnExp) { //后缀表达式计算 double[] Operands = new double[rpnExp.Length]; double x, y, v; Top = -1; string Operand = ""; for (int i = 0; i < rpnExp.Length; i++) { char c = rpnExp[i]; if ((c >= '0' && c <= '9') || c == '.') { Operand += c; } if ((c == ' ' || i == rpnExp.Length - 1) && Operand != "") //Update { Operands[++Top] = System.Convert.ToDouble(Operand); //push Operands Operand = ""; } if (c == '+' || c == '-' || c == '*' || c == '/') { if ((Operand != "")) { Operands[++Top] = System.Convert.ToDouble(Operand); //push Operands Operand = ""; } y = Operands[Top--]; //pop 双目运算符的第二操作数 (后进先出)注意操作数顺序对除法的影响 x = Operands[Top--]; //pop 双目运算符的第一操作数 switch (c) { case '+': v = x + y; break; case '-': v = x - y; break; case '*': v = x * y; break; case '/': v = x / y; // 第一操作数 / 第二操作数 注意操作数顺序对除法的影响 break; default: v = 0; break; } Operands[++Top] = v; //push 中间结果再次入栈 } } v = Operands[Top--]; //pop 最终结果 return v; } #endregion } |
|
|
