/// <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
}
联系客服