/// <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
}
1.先说明下这个实现算法--逆波兰表达式
表达式一般由操作数(Operand)、运算符(Operator)组成，例如算术表达式中，通常把运算符放在两个操作数的中间，
这称为中缀表达式(Infix Expression)，如A+B。
波兰数学家Jan Lukasiewicz提出了另一种数学表示法，它有两种表示形式：
把运算符写在操作数之前，称为波兰表达式(Polish Expression)或前缀表达式(Prefix Expression)，如+AB；
把运算符写在操作数之后，称为逆波兰表达式(Reverse Polish Expression)或后缀表达式(Suffix Expression)，如AB+；
其中，逆波兰表达式在编译技术中有着普遍的应用。
算法：
一、 将中缀表达式转换成后缀表达式算法：
1、从左至右扫描一中缀表达式。
2、若读取的是操作数，则判断该操作数的类型，并将该操作数存入操作数堆栈
3、若读取的是运算符
(1) 该运算符为左括号"("，则直接存入运算符堆栈。
(2) 该运算符为右括号")"，则输出运算符堆栈中的运算符到操作数堆栈，直到遇到左括号为止。
(3) 该运算符为非括号运算符：
(a) 若运算符堆栈栈顶的运算符为括号，则直接存入运算符堆栈。
(b) 若比运算符堆栈栈顶的运算符优先级高或相等，则直接存入运算符堆栈。
(c) 若比运算符堆栈栈顶的运算符优先级低，则输出栈顶运算符到操作数堆栈，并将当前运算符压入运算符堆栈。
4、当表达式读取完成后运算符堆栈中尚有运算符时，则依序取出运算符到操作数堆栈，直到运算符堆栈为空
示例：
（1.2+3.5）*2/4 =>1.2 3.5+ 2* 4/
下面给出实现代码：