中缀表达式转后缀表达式
1.声明队列Expressions，和堆栈Operators ，并定义优先级：
( 和 ):3
* 和/ : 2
+ 和 - :1
数值越大，优先级越高
foreach(每一个计算单元 in 当前中缀表达式)
{
2.遇到数字直接进队列
3.遇到左括号 '('直接进堆栈
4.遇到右括号
while(栈顶元素!=左括号)
{
入队列
弹出
}
弹出（为了弹出左括号）
5.遇到操作符
while(堆栈非空 AND 当前元素优先级 <= 栈顶元素优先级 AND 栈顶元素 != 左括号)
{
栈顶元素入队列
弹出栈顶元素
}
当前操作符入栈
}
6.弹出所有栈内操作符，入队列（别忘了还有哥们没入队呢！）
C# 完整实现：
private const string StartScope = "(";
private const string EndScrope = ")";
private const int MinPrior = -1;
private const int NotSupportedOperator = -3;
private const int FatalError = -4;
public string[] ConvertToRpn(string[] strArr)
{
var operators = new Stack<string>();
var expression = new Queue<string>();
foreach (var str in strArr)
{
if (IsNum(str))
expression.Enqueue(str);
else switch (str)
{
case StartScope:
operators.Push(str);
break;
case EndScrope:
{
if (operators.Count == 0)
return null;
while (operators.Count > 0 && operators.Peek() != StartScope)
{
expression.Enqueue(operators.Peek());
operators.Pop();
}
operators.Pop();
}
break;
default:
if (IsSupportedOperator(str))
{
var stackPrior = operators.Count == 0 ? MinPrior : OperatorPriority(operators.Peek());
var elementPrior = OperatorPriority(str);
if (elementPrior <= stackPrior)
{
while (operators.Count > 0 && OperatorPriority(operators.Peek()) >=
elementPrior && operators.Peek() != StartScope)
{
expression.Enqueue(operators.Peek());
operators.Pop();
}
}
operators.Push(str);
}
break;
}
}
while (operators.Count > 0)
{
expression.Enqueue(operators.Peek());
operators.Pop();
}
return expression.ToArray();
}
private bool IsNum(string str)
{
double rlt;
return double.TryParse(str, out rlt);
}
private int OperatorPriority(string op)
{
switch (op)
{
case "+":
case "-":
return 1;
case "*":
case "/":
return 2;
case StartScope:
case EndScrope:
return 3;
default:
return MinPrior;
}
}
private bool IsSupportedOperator(string str)
{
var supportedOps = new[] { "+", "-", "*", "/" };
return supportedOps.Contains(str);
}