数据结构和算法-中缀表达式转后缀表达式（c#）

标签：==   元素   sub   index   链表   ima   switch   cal   not   

介绍

支持数字类型、浮点类型运算表达式运算，看下面的案例

具体步骤

1）初始化两个栈：运算符栈s1和储存中间结果的栈s2；
2）从左至右扫描中缀表达式；
3）遇到操作数时，将其压s2；
4）遇到运算符时，比较其与s1栈顶运算符的优先级：
（1）如果s1为空，或栈顶运算符为左括号“(”，则直接将此运算符入栈；
（2）否则，若优先级比栈顶运算符的高，也将运算符压入s1；
（3）否则，将s1栈顶的运算符弹出并压入到s2中，再次转到(4-1)与s1中新的栈顶运算符相比较；
5）遇到括号时：
（1）如果是左括号“(”，则直接压入s1
（2）如果是右括号“)”，则依次弹出s1栈顶的运算符，并压入s2，直到遇到左括号为止，此时将这一对括号丢弃
6）重复步骤2至5，直到表达式的最右边
7）将s1中剩余的运算符依次弹出并压入s2
8）依次弹出s2中的元素并输出，结果的逆序即为中缀表达式对应的后缀表达式

客户端

 string expression = "1+((2+3)*40.5)-5.3";
//结果计算
 var result = PolandNotation.Calculate(expression);
 Console.WriteLine($"{expression}={result}");

助手类

    public class PolandNotation {
        /// 

        /// 计算
        /// 
        /// 
        /// 
        public static T Calculate(string expression)
        {
            //将中缀表达式转换成后缀表达式
            List suffixExpression = PolandNotation.ParseSuffixExpression(expression);

            //创建栈
            Stack stack = new Stack();

            //循环遍历
            suffixExpression.ForEach(item =>
            {
                string regex = GetRegex();
                if (Regex.IsMatch(item, regex))//"\\d+"
                {
                    //如果是数字直接入栈
                    stack.Push(item);
                }
                //如果是操作符
                else
                {
                    //出栈两个数字，并运算，再入栈
                    dynamic num1 = (T)Convert.ChangeType(stack.Pop(),typeof(T));

                    dynamic num2 = (T)Convert.ChangeType(stack.Pop(), typeof(T));

                    T result = default(T);

                    if (item.Equals("+"))
                    {
                        result = num2 + num1;
                    }
                    else if (item.Equals("*"))
                    {
                        result = num2 * num1;
                    }
                    else if (item.Equals("/"))
                    {
                        result = num2 / num1;
                    }
                    else if (item.Equals("-"))
                    {
                        result = num2 - num1;
                    }
                    else
                    {
                        throw new Exception("无法识别符号");
                    }

                    stack.Push("" + result);
                }
            });

            //最后把stack中数据返回
            return (T)Convert.ChangeType(stack.Pop(),typeof(T));
        }

        /// 

        /// 字符串转中缀表达式的List
        /// 
        /// 
        /// 
        private static List ToInfixExpression(string expression)
        {
            List list = new List();

            int index = 0;

            string str = "";

            do
            {

                //48-57ASCII码代表的是0-9 如果不是0-9直接入链表
                if (expression[index]  57)//ascii编码
                {
                    list.Add("" + expression[index]);

                    index++;
                }
                else
                {
                    str = "";

                    //多位数判断
                    while (index = 48 && expression[index] 
        /// 中缀转后缀
        /// 
        /// 
        /// 
        private static List ParseSuffixExpression(string expression)
        {
           List expressionList = ToInfixExpression(expression);

            //存储中间结果
            List list = new List();
            //符号栈
            Stack stack = new Stack();

            foreach (var item in expressionList)
            {
                //多位数判断 如果是数字直接加入list
                var regex = GetRegex();
                if (Regex.IsMatch(item, regex))//"\\d+"
                {
                    list.Add(item);
                }
                //如果是左括号，直接入符号栈
                else if (item.Equals("("))
                {
                    stack.Push(item);
                }
                //如果是右括号
                else if (item.Equals(")"))
                {
                    //依次弹出stack栈顶的运算符，并存入list,直到遇到左括号为止
                    while (!stack.Peek().Equals("("))
                    {
                        list.Add(stack.Pop());
                    }
                    //将(也出栈
                    stack.Pop();
                }
                //如果是*/+-
                else
                {
                    //循环判断item的优先级小于或者等于stack栈顶运算符，将stack栈顶的运算符出栈并加入到list中
                    while (stack.Count != 0 && Operation.GetValue(stack.Peek()) >= Operation.GetValue(item))
                    {
                        list.Add(stack.Pop());
                    }
                    //将item入栈
                    stack.Push(item);
                }
            }

            //将stack剩余的运算符依次入list
            while (stack.Count != 0)
            {
                list.Add(stack.Pop());
            }

            return list;
        }

        private static string GetRegex()
        {
            string regex = "\\d+";
           Type t = typeof(T);
            if (t == typeof(Int16) || t == typeof(Int32) || t == typeof(Int64))
            {
                regex = "\\d+";
            }
            else if (t==typeof(float)|| t == typeof(double) || t == typeof(decimal))
            {
                regex = "(\\d+\\.\\d+|\\d+)";
            }
            return regex;
        }
    }
    public class Operation
    {
        private static int ADD = 1;
        private static int SUB = 1;
        private static int MUL = 2;
        private static int DIV = 2;

        public static int GetValue(string operation)
        {
            int result = 0;

            switch (operation)
            {
                case "+":
                    result = ADD;
                    break;
                case "-":
                    result = SUB;
                    break;
                case "*":
                    result = MUL;
                    break;
                case "/":
                    result = DIV;
                    break;
                default:
                    // Console.WriteLine("不存在该运算符");
                    break;
            }

            return result;
        }
    }

数据结构和算法-中缀表达式转后缀表达式（c#）

标签：==   元素   sub   index   链表   ima   switch   cal   not   

原文地址：https://www.cnblogs.com/fanfan-90/p/13290776.html