背景

此文给出一个中缀表达式转变为逆波兰表达式（后缀表达式）的算法，算法实现的比较简单，特别是：词法分析部分是没有做的。

实现

1 using System;  2 using System.Collections.Generic;  3 using System.Linq;  4 using System.Text;  5 using System.Threading.Tasks;  6   7 namespace DataStuctureStudy.Stacks  8 {  9     public static class Calculator 10     { 11         private static readonly Dictionary
     
       _operators = new Dictionary
      
        12         { 13             { "+", 1 }, 14             { "-", 1 }, 15             { "*", 2 }, 16             { "/", 2 }, 17             { "%", 2 } 18         }; 19  20         public static void Test(string expression) 21         { 22             foreach (var item in GetPostfixTokens(GetTokens(expression))) 23             { 24                 Console.Write(item + " "); 25             } 26         } 27  28         private static IEnumerable
       
         GetPostfixTokens(IEnumerable
        
          infixTokens) 29         { 30             var postfixTokens = new List
         
          (); 31             var stack = new Stack
          
           (); 32 33 foreach (var token in infixTokens) 34 { 35 if (IsOperator(token)) 36 { 37 var curOperator = token; 38 39 if (stack.Count == 0) 40 { 41 stack.Push(curOperator); 42 } 43 else 44 { 45 while (stack.Count != 0) 46 { 47 var popOperator = stack.Pop(); 48 if (popOperator == "(") 49 { 50 stack.Push(popOperator); 51 break; 52 } 53 54 if (_operators[curOperator] <= _operators[popOperator]) 55 { 56 postfixTokens.Add(popOperator); 57 } 58 else 59 { 60 stack.Push(popOperator); 61 break; 62 } 63 } 64 65 stack.Push(curOperator); 66 } 67 } 68 else if (token == "(") 69 { 70 stack.Push(token); 71 } 72 else if (token == ")") 73 { 74 var popOperator = stack.Pop(); 75 while (popOperator != "(") 76 { 77 postfixTokens.Add(popOperator); 78 popOperator = stack.Pop(); 79 } 80 } 81 else 82 { 83 postfixTokens.Add(token); 84 } 85 } 86 87 while (stack.Count != 0) 88 { 89 postfixTokens.Add(stack.Pop()); 90 } 91 92 return postfixTokens; 93 } 94 95 private static IEnumerable
           
             GetTokens(string expression) 96 { 97 var tokens = new List
            
             (); 98 var sb = new StringBuilder(); 99 100 foreach (var item in expression)101 {102 if (IsOperator(item.ToString()) || item == '(' || item == ')')103 {104 if (sb.Length > 0)105 {106 tokens.Add(sb.ToString());107 sb.Clear();108 }109 110 tokens.Add(item.ToString());111 }112 else113 {114 sb.Append(item);115 }116 }117 118 return tokens;119 }120 121 private static bool IsOperator(string token)122 {123 return _operators.ContainsKey(token);124 }125 }126 }