C# 中的调车场算法仅在某些时候有效

本文关键字：候有效 有效 调车场 算法 | 更新日期: 2023-09-27 18:35:42

我正在研究从中缀表达式构建表达式树。目前我正在转换为后缀，然后构建树。我的代码适用于大多数表达式，但不是全部。我在括号的实现上做错了。这是我的代码-

readonly static char[] operators = { '+', '-', '*', '/' };
       string order_of_op(string op1, string op2)
       {
            if (op1 == "*" || op1 == "/")//is op1 higher?
            {
                return op1;//it is so return it
            }
            else if ((op2 == "*" || op2 == "/"))//is op2 higher
            {
                return op2;//it is so return it
            }
            else
                return op1;// they are both addition or subtraction so    return op1.
        }

        Queue<string> convert_to_postfix(string infix) //following the    Shunting-yard algorithm
        {
            Queue<string> num_queue = new Queue<string>();
            Stack<string> op_stack = new Stack<string>();
            Stack<string> temp_stack = new Stack<string>();
            string temp = "";
            foreach (char s in infix)
            {
                if (operators.Contains(s) == true)//if its a function push it on the stack
                {
                    if (temp != "")//make sure we don't push an empty string
                        num_queue.Enqueue(temp);
                    if (op_stack.Count != 0)//make sure we dont crash popping from empty stack
                    {
                        if (op_stack.Peek() != "(")//if we dont have a parenthese on top proceed as normal
                        {
                            if (op_stack.Count > 1)
                            {
                                while (op_stack.Count != 0 && order_of_op(op_stack.Peek(), s.ToString()) == op_stack.Peek())
                                {
                                    num_queue.Enqueue(op_stack.Pop());
                                }
                            }
                        }
                        op_stack.Push(s.ToString());
                    }
                    else
                    {
                        op_stack.Push(s.ToString());
                    }
                    temp = "";
                }
                else if (s == '(')
                {
                    op_stack.Push(s.ToString());
                }
                else if (s == ')')
                {
                    if (temp!= "")
                        num_queue.Enqueue(temp);
                    temp = "";
                    while (op_stack.Peek() != "(")
                    {
                        num_queue.Enqueue(op_stack.Pop());
                    }
                    op_stack.Pop();
                    if (op_stack.Count > 1)
                    {
                        if (operators.Contains(op_stack.Peek()[0]) == true)
                        {
                            num_queue.Enqueue(op_stack.Pop());
                        }
                    }
                }
                else
                {
                    temp += s;
                }
            }
            if (temp != "")
            {
                num_queue.Enqueue(temp);
            }
            foreach (string s in op_stack)
            {
                num_queue.Enqueue(s);
            }
            Console.Write("Postfix = ");
            foreach (string s in num_queue)
            {
                Console.Write(s);
            }
            Console.WriteLine();
            return num_queue;
        }

感谢您的任何帮助！

C# 中的调车场算法仅在某些时候有效

好吧，

我修好了！我所要改变的只是——

if (op_stack.Count > 1)

自

if (op_stack.Count >= 1)
相关文章：