1、需求输入“表达式”字符串，输出计算结果。
如输入字符串：“1+4+7+(6*2*4+3+6-5)+2”
输出：66
假设运算只有+、-、×、/、(、)。
2、分析（参考节选(c#)数据结构与算法分析 --栈与队列 ）首先了解一下计算机是怎么计算类似于 1*(2+3)+4/2 这样的计算。对于大脑来说，这个算式简单到不能再简单了，但是电脑却不是如此，得让它明白那个先算，那个后算，以及哪些是操作符（运算符）哪些不是（例如括号）。
像我们经常使用的这种算式称为
中缀式 ，就是运算符都在两个操作符中间了，这种中缀式对于我们人脑来说，并不是顺序执行的，它可以从中间先开始，比如1+2*3 ，这正是电脑很难理解中缀式的原因，因为他总是顺序执行的。那么，我们就得把中缀式换成
后缀式(postfix) 或称作
逆波兰记法(reverse Polish notation)。
中缀式就是把运算符放到两个操作数后边，让算式保持顺序计算（对于我们人脑也是如此）。具体怎么放，大家看看下面的例子就明白了。
|
中缀式
|
后缀式
|
| A+B+C-D |
A B+C+D- |
| A*B/C+D |
A B*C/D+ |
| A*(B+C*D)+E |
A B C D * + * E + |
| (A+B)*C/(D+E-F) |
A B + C * D E + F - / |
| A+B*C+(D*E+F)*G |
A B C * + D E * F + G * + |
结合上边的示例，会发现后缀式并没有描述优先级的括号。
使用
后缀式，计算方向从左到右，遇到运算符，就计算运算符前2个数字，然后把结果替换这3者（2个数字和符号）位置。
如AB+C+D-
遇到第一个“+”，计算A+B，假设得到结果Z，后缀式就更新为
ZC+D-
如此类推，得到最后的结果。
3、实现代码
public class ExpressionCalulate
{
/// <summary>
/// 定义优先级
/// </summary>
private static Dictionary<char, int> Priority = new Dictionary<char, int>();
static ExpressionCalulate()
{
Priority.Add('+', 1);
Priority.Add('-', 1);
Priority.Add('*', 2);
Priority.Add('/', 2);
Priority.Add('(', 3);
Priority.Add(')', 3);
}
/// <summary>
/// 计算表达式
/// </summary>
/// <param name="expression"></param>
/// <returns></returns>
public static decimal Calulate(string expression)
{
return CalulatePostfix(ConvertToPostfix(expression));
}
/// <summary>
/// 计算后缀式字符串
/// </summary>
/// <param name="postfixExpression"></param>
/// <returns></returns>
public static decimal CalulatePostfix(string postfixExpression)
{
Stack<decimal> numbers = new Stack<decimal>();
string[] expressions = postfixExpression.Split(new char[] { ' ' }, StringSplitOptions.RemoveEmptyEntries);
foreach (string expression in expressions)
{
if (expression.Length == 1 && Priority.ContainsKey(expression[0]))
{
//计算
decimal number2 = numbers.Pop();
decimal number1 = numbers.Pop();
numbers.Push(EasyCaluate(number1, number2, expression[0]));
}
else
{
numbers.Push(Convert.ToDecimal(expression));
}
}
return numbers.Pop();
}
/// <summary>
/// 把表达式转换为后缀式
/// </summary>
/// <param name="expression"></param>
/// <returns></returns>
public static string ConvertToPostfix(string expression)
{
//初始化存储结果的后缀式数组
char[] results = new char[expression.Length * 2];
//临时存放运算符
Stack<char> s = new Stack<char>(expression.Length);
//当前存放results的索引值
int currentResultCursorIndex = 0;
//遍历表达式
foreach (char c in expression)
{
if (!Priority.ContainsKey(c))
{
//如果不是运算符，直接输出结果
results[currentResultCursorIndex++] = c;
}
else
{
//如果是符号，先用' '隔开，方便区隔数字和运算符
results[currentResultCursorIndex++] = ' ';
//如果遇到右括号，即是出现一对括号，输出这对括号的运算符
if(c == ')' && s.Count > 0)
{
char pop = default(char);
while (pop != '(')
{
pop = s.Pop();
if (pop != '(' && pop != ')')
{
results[currentResultCursorIndex++] = pop;
results[currentResultCursorIndex++] = ' ';
}
}
continue;
}
//判断当前运算符的优先级
int priority = Priority[c];
int peekPriority = -1;
//之前的运算符优先级
if (s.Count > 0)
{
peekPriority = Priority[s.Peek()];
}
//当前与之前的运算符优先级做比较
if (priority > peekPriority || peekPriority == Priority['('])
{
//如果当前优先级大于之前的运算符优先级或者遇到第一个括号，就先把运算符存起来
s.Push(c);
}
else
{
//否则，输出存储的运算符
while (s.Count > 0 && s.Peek() != '(')
{
results[currentResultCursorIndex++] = s.Pop();
results[currentResultCursorIndex++] = ' ';
}
s.Push(c);
}
}
}
//最后把所有运算符输出
while (s.Count > 0)
{
results[currentResultCursorIndex++] = ' ';
results[currentResultCursorIndex++] = s.Pop();
}
//返回结果字符串
return new string(results).TrimEnd('\0');
}
private static decimal EasyCaluate(decimal d1, decimal d2, char opt)
{
decimal result = 0;
switch (opt)
{
case '+': { result = decimal.Add(d1, d2); break; }
case '-': { result = decimal.Subtract(d1, d2); break; }
case '*': { result = decimal.Multiply(d1, d2); break; }
case '/': { result = decimal.Divide(d1, d2); break; }
}
return result;
}
执行：
Console.WriteLine(ExpressionCalulate.Calulate("1+2+3*3-2")); //10
Console.WriteLine(ExpressionCalulate.Calulate("1+4+7+(6*2*4+3+6-5)+2")); //66
Console.WriteLine(ExpressionCalulate.Calulate("1+4+7+(6*2*(4+3)+6-5)+2")); //99
Console.WriteLine(ExpressionCalulate.Calulate("1+4/7+(6*2*(4+3)+6-5)+2")); //88.571428571428571428571428571429
4、参考：
(c#)数据结构与算法分析 --栈与队列