【代码笔记】【c#】中缀表达式转后缀表达式

一时失言乱红尘 2022-11-28 13:18 178阅读 0赞

/// <summary>
    		/// 中缀表达式转后缀表达式
    		/// </summary>
    		/// <param name="infix">不需用空格隔开的常规中缀表达式</param>
    		/// <returns></returns>
    		public static string InToSu(String infix) { 
    
    			//将表达式区分数与运算符以空格拆分，得到字符串数组
    			String infixFmt = "";
    			infix.ToList().ForEach(chr=> { 
    				if (char.IsDigit(chr) || chr == '.')
    					infixFmt += chr;
    				else
    					infixFmt += " " + chr + " ";
    			});
    			
    			//ps:如果业务规则不允许太多括号嵌套的话 可以通过在这里控制匹配空格量实现
    			string[] infixFmts = Regex.Replace(infixFmt, @"\s+", " ").Split(' ');
    
    			Stack<string> op = new Stack<string>(); //存放运算符的栈
    			StringBuilder outStr = new StringBuilder(); //最终后缀表达式
    			foreach (string unitStr in infixFmts)
    			{ 
    				if (isNumberic(unitStr))
    				{ 
    					//是数则直接输出
    					outStr.AppendWithSpace(unitStr);
    				}
    				else 
    				{ 
    					//是正括号则入栈
    					if (unitStr == "(")
    					{ 
    						op.Push(unitStr);
    					}
    					else 
    					{ 
    						if (unitStr == ")")
    						{ 
    							if (op.Count <= 0)
    								throw new ArgumentException("表达式不合法");
    
    							//是反括号则出栈栈中元素并输出直到找到正括号 正括号不输出但要出栈
    							string o = "";
    							while (o != "(")
    							{ 
    								o = op.Pop();
    								if (o == "(") break;
    								outStr.AppendWithSpace(o);
    							}
    						}
    						else
    						{ 
    							//栈中一个运算符没有就入栈
    							if (op.Count == 0)
    							{ 
    								op.Push(unitStr);
    							}
    							else
    							{ 
    								//有则判断优先级
    								if (priorityCompare(unitStr, op.First())) 
    								{ 
    									//当前优先级高于栈顶元素优先级 则压入
    									op.Push(unitStr);
    								}
    								else
    								{ 
                                        //当前优先级小于等于栈顶元素优先级 则出栈栈中元素并输出 直到碰到正括号 正括号不出栈 最后压入当前的元素
                                        do
                                        { 
                                            if (op.Peek() == "(") break;
                                            outStr.AppendWithSpace(op.Pop());
                                        } while (op.Count > 0 && !priorityCompare(unitStr, op.Peek()));
                                        op.Push(unitStr);
    								}
    							}
    						}
    					}	
    				}
    			}
    			//输出剩下的栈中元素
    			int c = op.Count;
    			for (int i = 0; i < c; i++)
    				outStr.AppendWithSpace(op.Pop());
    
    			return outStr.ToString();
    		}

AppendWithSpace

public static class StringBuilderExt
        { 
            /// <summary>
            /// 添加元素后加一个空格
            /// </summary>
            /// <param name="stringBuilder"></param>
            /// <param name="str"></param>
            public static StringBuilder AppendWithSpace(this StringBuilder stringBuilder, object str)
            { 
                return stringBuilder.AppendFormat("{0} ", str);
            }
        }

priorityCompare

/// <summary>
    		/// 比较优先级 前者大为真 否则为假
    		/// </summary>
    		/// <param name="op"></param>
    		/// <param name="op2"></param>
    		/// <returns></returns>
    		public static Boolean priorityCompare(string op,string op2)//符号优先级
    		{ 
    			if (!"+-*/()".Contains(op) || !"+-*/()".Contains(op2))
    				throw new ArgumentException("错误的运算符");
    
    			int p1 = (op == "*" || op == "/")? 2 : (op == "+" || op == "-") ? 1 : 0;
    			int p2 = (op2 == "*" || op2 == "/") ? 2 : (op2 == "+" || op2 == "-") ? 1 : 0;
    
    			if (p1 > p2)
    				return true;
    			else
    				return false;
    		}

使用：

InToSu("11+4*(3+(3-(9/3-2)))+10/2")
    
    输出：
    11 4 3 3 9 3 / 2 - - + * + 10 2 / +