一个简单的 C# 编写的，中缀转逆波兰表示法的转换器
3.03/5 (10投票s)
将中缀表达式转换为逆波兰表示法
引言
本文介绍的类可用于将数学表达式从中缀表示法转换为逆波兰表示法。默认情况下，不对表达式进行验证，但可以通过 Options 参数开启一些简单的验证。
有关更多信息，请参阅 Shunting yard 算法。
背景
我需要在我的 Rational 类型的 ParseInfix 方法中使用它。
该类仅公开一个 public 方法：InfixToRpn 方法。
string result = PIEBALD.Lib.InfixToRpn
(
source
,
PIEBALD.Lib.InfixToRpn.RpnOptions.None
) ;
string result = PIEBALD.Lib.InfixToRpn
(
source
,
PIEBALD.Lib.InfixToRpn.RpnOptions.FailOnMalformedExpression
) ;
支持数学运算符（+、-、*、/、%、^（幂））和括号。
可以使用 ‘ (ASCII 96) 和 ’ 分隔符指定字面量文本（可用于科学记数法中的项）。
支持的字符
文件中还包含以下内容
RpnOptions
此枚举用于使用户能够控制 InfixToRpn 方法的一些可选功能。
RetainWhiteSpace
保留源字符串中的空格、控制字符和 null 字符。
FailOnMismatchedParenthesis
如果检测到不匹配的括号，则抛出 InfixToRpnFormatException 。
FailOnMalformedExpression
当发生其他各种情况时，抛出 InfixToRpnFormatException 。
全部
所有选项。
无
无选项。
InfixToRpnFormatException
如果指定了 FailOnMismatchedParenthesis 和/或 FailOnMalformedExpression 并且检测到该条件，则会抛出此异常的实例。该类有一个名为 Position 的 public 只读字段，其中包含似乎是错误的字符的（从一开始计数的）位置。
OperatorPrecedence
此枚举用于在以下类中为运算符关联优先级。
运算符
Operator 类的实例仅包含运算符字符及其优先级值。
OperatorStack
OperatorStack 是一个 Stack<Operator>。它有自己的 Push 和 Clear 版本，这些版本会将移除的 Operator 直接附加到输出。
OperatorStackStack
OperatorStackStack 是一个 Stack<OperatorStack>。InfixToRpn 方法使用其中一个，该方法使用一个 OperatorStack 进行初始化。每个 OperatorStack 代表一对括号。每次遇到左括号时，都会实例化一个新的 OperatorStack 并将其推送到 OperatorStackStack 上。每次遇到右括号时，顶部 OperatorStack 都会被弹出并清除（最底层的 OperatorStack 不会被弹出）。
ValidatorState
此枚举定义了验证器的状态。
NoMoreOpsAllowed
我们遇到了第二个运算符。
OnlyOneOpAllowed
我们遇到了一个左括号。
UnaryOpAllowed
我们遇到了第一个运算符。
BinaryOpAllowed
我们遇到了一个右括号。
TermBegun
我们遇到了一个项字符。
TermEnded
我们遇到了一个结束项的空格运算符。
VerbatimTextBegun
进入字面量文本模式。
InfixToRpn
该方法相当冗长，所以我不会全部展示。它主要包含一个遍历 Subject string 字符的 foreach 循环和一个 switch 语句。以下是主要部分（result 是一个 StringBuilder 成员字段）。
OperatorStackStack ops = new OperatorStackStack ( new OperatorStack ( 0 ) ) ;
int index = 0 ;
ValidatorState validatorstate = ValidatorState.OnlyOneOpAllowed ;
result.Length = 0 ;
result.EnsureCapacity ( Subject.Length * 2 ) ;
foreach ( char thischar in Subject )
{
index++ ;
switch ( thischar )
{
// See below
}
while ( ops.Count > 0 )
{
ops.Pop().Clear() ;
}
return ( result.ToString() ) ;
}
在 switch 语句内部（当然）有 case 语句，用于处理需要解释的各种字符。以下是乘法、除法和取模的 case 语句。
case '*' :
case '/' :
case '%' :
{
if ( failonmalformedexpression )
{
if
(
( validatorstate == ValidatorState.UnaryOpAllowed )
||
( validatorstate == ValidatorState.NoMoreOpsAllowed )
)
{
throw ( new InfixToRpnFormatException
(
"Too many operators in a row"
,
index
) ) ;
}
}
ops.Peek().Push
(
new Operator ( thischar , OperatorPrecedence.Medium )
) ;
validatorstate = ValidatorState.UnaryOpAllowed ;
break ;
}
以下是加法、减法、一元正号和一元负号的 case 语句。请注意，一元运算符的优先级最高，而其二元对应物的优先级较低。
case '-' :
case '+' :
{
if ( failonmalformedexpression )
{
if ( validatorstate == ValidatorState.NoMoreOpsAllowed )
{
throw ( new InfixToRpnFormatException
(
"Too many operators in a row"
,
index
) ) ;
}
}
if
(
( validatorstate == ValidatorState.UnaryOpAllowed )
||
( validatorstate == ValidatorState.OnlyOneOpAllowed )
)
{
/* Unary */
ops.Peek().Push
(
new Operator ( thischar , OperatorPrecedence.Highest )
) ;
validatorstate = ValidatorState.NoMoreOpsAllowed ;
}
else
{
/* Binary */
ops.Peek().Push
(
new Operator ( thischar , OperatorPrecedence.Low )
) ;
validatorstate = ValidatorState.UnaryOpAllowed ;
}
break ;
}
左括号会导致一个新的 OperatorStack 被推送到 OperatorStackStack 上。以下是左括号的 case 语句。
case '(' :
{
if ( failonmalformedexpression )
{
if
(
( validatorstate == ValidatorState.TermBegun )
||
( validatorstate == ValidatorState.TermEnded )
||
( validatorstate == ValidatorState.BinaryOpAllowed )
)
{
throw ( new InfixToRpnFormatException
(
"No operator preceding left-parenthesis"
,
index
) ) ;
}
}
ops.Push ( new OperatorStack ( index ) ) ;
validatorstate = ValidatorState.OnlyOneOpAllowed ;
break ;
}
右括号会导致顶部的 OperatorStack 从 OperatorStackStack 弹出（除非它是唯一的 OperatorStack），并被 Cleared。以下是右括号的 case 语句。
case ')' :
{
if ( failonmalformedexpression )
{
if
(
( validatorstate == ValidatorState.UnaryOpAllowed )
||
( validatorstate == ValidatorState.NoMoreOpsAllowed )
)
{
throw ( new InfixToRpnFormatException
(
"Operator followed by right-parenthesis"
,
index
) ) ;
}
if ( validatorstate == ValidatorState.OnlyOneOpAllowed )
{
throw ( new InfixToRpnFormatException
(
"Empty parentheses"
,
index
) ) ;
}
}
if ( ops.Count == 1 )
{
if ( failonmismatchedparenthesis )
{
throw ( new InfixToRpnFormatException
(
"Mismatched right-parenthesis"
,
index
) ) ;
}
ops.Peek().Clear() ;
}
else
{
ops.Pop().Clear() ;
}
validatorstate = ValidatorState.BinaryOpAllowed ;
break ;
}
我将展示的最后一个 case 是表达式的项，即操作数。项基本上是任何连续的字符，它们既不是运算符也不是空格。（字面量文本构成一个项，并且可能包含运算符字符和空格；但字面量文本有其特殊的处理方式，在此不予介绍。）
default :
{
if ( failonmalformedexpression )
{
if ( validatorstate == ValidatorState.BinaryOpAllowed )
{
throw ( new InfixToRpnFormatException
(
"No operator preceding term"
,
index
) ) ;
}
if ( validatorstate == ValidatorState.TermEnded )
{
throw ( new InfixToRpnFormatException
(
"Second consecutive term detected"
,
index
) ) ;
}
}
result.Append ( thischar ) ;
validatorstate = ValidatorState.TermBegun ;
break ;
}
Using the Code
Zip 文件还包含 Rpn.cs，这是一个非常简单的控制台程序。请使用您选择的 C# 编译器编译它和 LibRpn.cs。
示例输出
C:\>rpn 2+3*4
2 3 4 * +
C:\>rpn a/b-c
a b / c -
C:\>rpn x * -4
x
C:\>rpn "x * -4"
x 0 4 - *
C:\>rpn "x - -4"
x 0 4 - -
C:\>rpn "x - 1/4"
x 1 4 / -
C:\>rpn "x - /4"
Too many operators in a row at position 5
C:\>rpn "x ---4"
Too many operators in a row at position 5
历史
- 首次发布 - 2006-01-16
- 更新 - 2006-11-27
- 更新 - 2009-03-10 - 重写了文章。代码只有细微的改动，主要是注释。