中缀表达式和后缀表达式学习心得

中缀表达式(Infix expression)即符合a op b的格式，后缀表达式(Post Fix expression)即符合a b op 的格式。为什么要有后缀表达式？原因在于后缀表达式可以很容易的被计算机理解。

举个例子，a*(b+c)/d, 转化为后缀表达式是abc+*d/, 计算机会用栈来解释执行该表达式。

如果我是计算机，对于后缀表达式输入，会做如下事情：

computer will scan each characters in the expression
put abc to the stack, a, b, c
Meet +, pop two operands, b+c, push sum of b and c to the stack
meet *, pop two operands, sum * a, put sum*a to the stack
meet d, push d to stack
meet /, pop d and sum*a, calc sum*a/d
put the result to the stack. Done. the top of stack is the final result

既然后缀表达式对计算机如此有用，那么当计算机遇到中缀表达式时，转化成后缀表达式就是"one common ask”.

下面是实现代码，借助了栈来实现，栈里面只存操作符，操作数都是直接输出。

扫描的字符分以下几种

数字或字母
左括号或者右括号
操作符，+ - × /

入栈的情况包括

栈为空，目标扫描字符是一个操作符
目标字符是左括号
栈不为空，目标扫描字符优先级大于栈顶元素

出栈的情况包括：

目标字符是右括号，此时要一直pop直到发现左括号
目标字符优先级小于栈顶元素，pop之

特点

转化过程中括号全部消失，后缀表达式的目的就在于让计算机更好的理解优先级
能在栈里呆住的都是predence 极高的操作符
扫描完毕后，不要忘了栈里还可能有优先级很高的操作符，append 之

       public static string ConvertInfixToPostFix(string expression)
        {
            StringBuilder result = new StringBuilder();

if (string.IsNullOrEmpty(expression))
            {
return string.Empty;
            }

            Stack<char> stack = new Stack<char>();
var chars = expression.ToCharArray();
for (int i = 0; i < chars.Length; i++)
            {
if (char.IsLetterOrDigit(chars[i]))
                {
                    result.Append(chars[i]);
                }
else if (chars[i] == '(')
                {
                    stack.Push(chars[i]);
                }
else if (chars[i] == ')')
                {
while(stack.Count != 0 && stack.Peek() != '(')
                    {
                        result.Append(stack.Pop());
                    }

if(stack.Count != 0 && stack.Peek() != '(')
                    {
return "Invalid Experssion";
                    }
else
                    {
                        stack.Pop();
                    }
                }
// operator
else
                {
while (stack.Count != 0 && Priority(chars[i]) <= Priority(stack.Peek()))
                    {
                        result.Append(stack.Pop());
                    }

if (stack.Count == 0 || Priority(chars[i]) > Priority(stack.Peek()))
                    {
                        stack.Push(chars[i]);
                    }
                }
            } // end of for loop

while (stack.Count != 0)
            {
                result.Append(stack.Pop());
            }

return result.ToString();
        }

秒客网

中缀表达式和后缀表达式学习心得

相关文章