1本文目标
分析用堆栈解析算术表达式的基本方法。给出的示例代码能解析任何包括+，-，*，/，()和0到9数字组成的算术表达式。
2中缀表达式和后缀表达式
中缀表达式就是通常所说的算术表达式，比如(1+2)*3-4。
后缀表达式是指通过解析后，运算符在运算数之后的表达式，比如上式解析成后缀表达式就是12+3*4-。这种表达式可以直接利用栈来求解。
3运算符的优先级
| 优先级 |
运算符 |
| 1 |
括号() |
| 2 |
负号- |
| 3 |
乘方** |
| 4 |
乘*，除/，求余% |
| 5 |
加+，减- |
| 6 |
小于<，小于等于<=，大于>，大于等于>= |
| 7 |
等于==，不等于!= |
| 8 |
逻辑与&& |
| 9 |
逻辑或|| |
大致的规律是，一元运算符 > 二元运算符 > 多元运算符。
4利用堆栈解析算术表达式的过程
中缀表达式翻译成后缀表达式的方法如下：
（1）从左向右依次取得数据ch。
（2）如果ch是操作数，直接输出。
（3）如果ch是运算符（含左右括号），则：
a：如果ch = '('，放入堆栈。
b：如果ch = ')'，依次输出堆栈中的运算符，直到遇到'('为止。
c：如果ch不是')'或者'('，那么就和堆栈顶点位置的运算符top做优先级比较。
1：如果ch优先级比top高，那么将ch放入堆栈。
2：如果ch优先级低于或者等于top，那么输出top，然后将ch放入堆栈。
（4）如果表达式已经读取完成，而堆栈中还有运算符时，依次由顶端输出。
如果我们有表达式(A-B)*C+D-E/F，要翻译成后缀表达式，并且把后缀表达式存储在一个名叫output的字符串中，可以用下面的步骤。
（1）读取'('，压入堆栈，output为空
（2）读取A，是运算数，直接输出到output字符串，output = A
（3）读取'-'，此时栈里面只有一个'('，因此将'-'压入栈，output = A
（4）读取B，是运算数，直接输出到output字符串，output = AB
（5）读取')'，这时候依次输出栈里面的运算符'-'，然后就是'('，直接弹出，output = AB-
（6）读取'*'，是运算符，由于此时栈为空，因此直接压入栈，output = AB-
（7）读取C，是运算数，直接输出到output字符串，output = AB-C
（8）读取'+'，是运算符，它的优先级比'*'低，那么弹出'*'，压入'+"，output = AB-C*
（9）读取D，是运算数，直接输出到output字符串，output = AB-C*D
（10）读取'-'，是运算符，和'+'的优先级一样，因此弹出'+'，然后压入'-'，output = AB-C*D+
（11）读取E，是运算数，直接输出到output字符串，output = AB-C*D+E
（12）读取'/'，是运算符，比'-'的优先级高，因此压入栈，output = AB-C*D+E
（13）读取F，是运算数，直接输出到output字符串，output = AB-C*D+EF
（14）原始字符串已经读取完毕，将栈里面剩余的运算符依次弹出，output = AB-C*D+EF/-
5计算算术表达式
当有了后缀表达式以后，运算表达式的值就非常容易了。可以按照下面的流程来计算。
（1）从左向右扫描表达式，一个取出一个数据data
（2）如果data是操作数，就压入堆栈
（3）如果data是操作符，就从堆栈中弹出此操作符需要用到的数据的个数，进行运算，然后把结果压入堆栈
（4）如果数据处理完毕，堆栈中最后剩余的数据就是最终结果。
比如我们要处理一个后缀表达式1234+*+65/-，那么具体的步骤如下。
（1）首先1，2，3，4都是操作数，将它们都压入堆栈
（2）取得'+'，为运算符，弹出数据3，4，得到结果7，然后将7压入堆栈
（3）取得'*'，为运算符，弹出数据7，2，得到数据14，然后将14压入堆栈
（4）取得'+'，为运算符，弹出数据14，1，得到结果15，然后将15压入堆栈
（5）6，5都是数据，都压入堆栈
（6）取得'/'，为运算符，弹出数据6，5，得到结果1.2，然后将1.2压入堆栈
（7）取得'-'，为运算符，弹出数据15，1.2，得到数据13.8，这就是最后的运算结果
6 示例代码
///
<summary>
///
将中缀表达式翻译成后缀表达式
///
输入中缀表达式： A+B*(C+D)-E/F
///
翻译成后缀表达式：ABCD+*+EF/-
///
中缀表达式翻译成后缀表达式的方法如下：
///
（1）从左向右依次取得数据ch
///
（2）如果ch是操作数，直接输出
///
（3）如果ch是运算符（含左右括号），则：
///
a：如果ch
= '('，放入堆栈
///
b：如果ch
= ')'，依次输出堆栈中的运算符，直到遇到'('为止
///
c：如果ch不是')'或者'('，那么就和堆栈顶点位置的运算符top做优先级比较
///
1：如果ch优先级比top高，那么 将ch放入堆栈
///
2：如果ch优先级低于或者等于top，那么输出top，然后将ch放入堆栈
///
（4）如果表达式已经读取完成，而堆栈中还有运算符时，依次由顶端输出
///
</summary>
public
class
PosfixParser
{
private
static
string expression
= "1+4/(1+1)+2*(3+4)-6/3+5/(1/2+2/1)";
private
static
Stack myStack =
new Stack();
private
static
StringBuilder posfixExpression =
new
StringBuilder();
public
static
void Main()
{
Console.WriteLine("This
Midfix expression is: {0}",
expression);
Console.WriteLine("The
Posfix expression is: {0}",
Parse());
Console.WriteLine("The
result is {0}",
Calculate());
Console.Read();
}
//将中缀表达式解析成后缀表达式
public
static
string Parse()
{
int
i, j =
0;
char
ch, ch1;
char[]
A =
expression.ToCharArray(); //将字符串转成字符数组，要注意的是，不能有大于10的数存在
char[]
B =
new char[A.Length];
//最后生成的后缀表达式会小于这个长度，因为有括号
int
length =
A.Length;
for(i=0;
i<length;
i++)
{
ch
= A[i];
if(
IsOperand( ch ) ) //如果是操作数，直接放入B中
{
B[j++]
= ch;
}
else
{
if(
ch ==
'('
) //如果是'('，将它放入堆栈中
myStack.Push(ch);
else
if(
ch ==
')')
//如果是')'
{
while(
!IsEmpty(myStack)
) //不停地弹出堆栈中的内容，直到遇到'('
{
ch
= (char)myStack.Pop();
if(
ch ==
'('
)
break;
else
B[j++]
= ch;
//将堆栈中弹出的内容放入B中
}
}
else
//既不是'('，也不是')'，是其它操作符，
比如+, -, *, /之类的
{
if(
!IsEmpty(
myStack ) )
{
do
{
ch1
= (char)myStack.Pop();//弹出栈顶元素
if(Priority(ch)
> Priority(ch1))
//如果栈顶元素的优 先级小于读取到的操作符
{
myStack.Push(ch1);//将栈顶元素放回堆栈
myStack.Push(ch);//将读取到的操作符放回堆栈
break;
}
else//如果栈顶元素的优先级比较高或者两者相等时
{
B[j++]
= ch1;
//将栈顶元素弹出，放入B中
if(
IsEmpty(myStack) )
{
myStack.Push(ch);
//将读取到的操作符压入堆栈中
break;
}
}
}
while(
!IsEmpty(myStack));
}
else
//如果堆栈为空，就把操作符放入堆栈中
{
myStack.Push(ch);
}
}
}
}
while(
!IsEmpty(myStack
) )
B[j++]
= (char)myStack.Pop();//将堆栈中剩下的操作符输出到B中
for(i=0;
i<B.Length;
i++)
if(
B[i] !=
'\0'
) //去除多余的空字符
posfixExpression.Append(B[i]);
return
posfixExpression.ToString();
}
6 示例代码
/// <summary>
/// 将中缀表达式翻译成后缀表达式
/// 输入中缀表达式： A+B*(C+D)-E/F
/// 翻译成后缀表达式：ABCD+*+EF/-
/// 中缀表达式翻译成后缀表达式的方法如下：
/// （1）从左向右依次取得数据ch
/// （2）如果ch是操作数，直接输出
/// （3）如果ch是运算符（含左右括号），则：
/// a：如果ch = '('，放入堆栈
/// b：如果ch = ')'，依次输出堆栈中的运算符， 直到遇到'('为止
/// c：如果ch不是')'或者'('，那么就和堆栈顶点 位置的运算符top做优先级比较
/// 1：如果ch优先级比top高，那么 将ch放入堆栈
/// 2：如果ch优先级低于或者等于 top，那么输出top，然后将ch放入堆栈
/// （4）如果表达式已经读取完成，而堆栈中还有运算符时，依次由顶端输出
/// </summary>
public class PosfixParser
{
private static string expression = "1+4/(1+1)+2*(3+4)-6/3+5/(1/2+2/1)";
private static Stack myStack = new Stack();
private static StringBuilder posfixExpression = new StringBuilder();
public static void Main()
{
Console.WriteLine("This Midfix expression is: {0}", expression);
Console.WriteLine("The Posfix expression is: {0}", Parse());
Console.WriteLine("The result is {0}", Calculate());
Console.Read();
}
//将中缀表达式解析成后缀表达式
public static string Parse()
{
int i, j = 0;
char ch, ch1;
char[] A = expression.ToCharArray(); //将字符串转成字符数组，要注意的是，不能有大于10的数存在
char[] B = new char[A.Length]; //最后生成的后缀表达式会小于这个长度，因为有括号
int length = A.Length;
for(i=0; i<length; i++)
{
ch = A[i];
if( IsOperand( ch ) ) //如果是操作数，直接放入B中
{
B[j++] = ch;
}
else
{
if( ch == '(' ) //如果是'('，将它放入堆栈中
myStack.Push(ch);
else if( ch == ')') //如果是')'
{
while( !IsEmpty(myStack) ) //不停地弹出堆栈中的内容，直到遇到'('
{
ch = (char)myStack.Pop();
if( ch == '(' )