基于Shunting Yard算法的PEMDAS计算器括号计算异常求助

问题现象 #

计算表达式5*2+(5*10)/5时返回结果52，正确结果应为20。问题表现为：括号内5*10=50计算正确，但后续运算未遵循PEMDAS规则，错误执行(5*2)/5 + 50而非正确的(5*2)+(50/5)。

当前代码实现 #

evaluate函数 #

public double evaluate(string expression)
{
    Stack<double> operandStack = new Stack<double>();
    Stack<char> operatorStack = new Stack<char>();
    Queue<string> outputQueue = new Queue<string>();

    for (int i = 0; i < expression.Length; i++)
    {
        char c = expression[i];

        if (char.IsDigit(c) || c == '.')
        {
            string operand = "";
            while (i < expression.Length && (char.IsDigit(expression[i]) || expression[i] == '.'))
            {
                operand += expression[i];
                i++;
            }
            outputQueue.Enqueue(operand);
            i--;
        }
        else if (c == '+' || c == '-' || c == '*' || c == '/' || c == '%' || c == '^')
        {
            while (operatorStack.Count > 0 && HasHigherPrecedence(c, operatorStack.Peek()))
            {
                outputQueue.Enqueue(operatorStack.Pop().ToString());
            }
            operatorStack.Push(c);
        }
        else if (c == '(')
        {
            string subExpression = "";
            int parenthesesCount = 1;
            for (int j = i + 1; j < expression.Length; j++)
            {
                char subChar = expression[j];
                if (subChar == '(')
                {
                    parenthesesCount++;
                }
                else if (subChar == ')')
                {
                    parenthesesCount--;
                }
                if (parenthesesCount == 0)
                {
                    subExpression = expression.Substring(i + 1, j - i - 1);
                    i = j;
                    break;
                }
            }
            double subResult = evaluate(subExpression);
            outputQueue.Enqueue(subResult.ToString());
        }
    }

    while (operatorStack.Count > 0)
    {
        outputQueue.Enqueue(operatorStack.Pop().ToString());
    }

    while (outputQueue.Count > 0)
    {
        string item = outputQueue.Dequeue();
        if (double.TryParse(item, out double operand))
        {
            operandStack.Push(operand);
        }
        else
        {
            if (operandStack.Count < 2)
            {
                throw new Exception("Not enough operands on the stack.");
            }
            double operand2 = operandStack.Pop();
            double operand1 = operandStack.Pop();

            switch (item)
            {
                case "+":
                    operandStack.Push(operand1 + operand2);
                    break;
                case "-":
                    operandStack.Push(operand1 - operand2);
                    break;
                case "*":
                    operandStack.Push(operand1 * operand2);
                    break;
                case "/":
                    operandStack.Push(operand1 / operand2);
                    break;
                case "%":
                    operandStack.Push(operand1 % operand2);
                    break;
                case "^":
                    operandStack.Push(Math.Pow(operand1, operand2));
                    break;
            }
        }
    }

    return operandStack.Pop();
}

优先级判断函数HasHigherPrecedence #

private bool HasHigherPrecedence(char currentOperator, char stackOperator)
{
    if (stackOperator == '(' || stackOperator == ')')
    {
        return false;
    }
    if ((currentOperator == '*' || currentOperator == '/' || currentOperator == '%') && (stackOperator == '+' || stackOperator == '-'))
    {
        return true;
    }
    if ((currentOperator == '^') && (stackOperator != '^'))
    {
        return true;
    }
    if (currentOperator == '+' || currentOperator == '-')
    {
        if (stackOperator == '+' || stackOperator == '-')
        {
            return true;
        }
        else
        {
            return false;
        }
    }
    return false;
}

问题根源 #

核心错误在于优先级判断逻辑与Shunting Yard算法的要求完全相反：

• 原HasHigherPrecedence函数判断的是「当前运算符是否比栈顶运算符优先级高」，但算法要求的是判断「栈顶运算符是否比当前运算符优先级更高（或相等，左结合时）」。
• 原循环条件会导致高优先级运算符被压栈而非优先弹出，打乱运算顺序。
• 原函数未明确区分左结合（+、-、*、/、%）和右结合（^）的处理规则，同优先级运算符的执行顺序错误。

修复方案 #

1. 重构优先级判断逻辑 #

替换原HasHigherPrecedence函数，明确优先级层级与结合性：

private bool ShouldPopStackOperator(char currentOp, char stackOp)
{
    int currentPrecedence = GetOperatorPrecedence(currentOp);
    int stackPrecedence = GetOperatorPrecedence(stackOp);

    // 左结合运算符：优先级相等时弹出栈顶（先执行）
    // 右结合运算符（^）：优先级相等时不弹出（后执行）
    if (currentOp == '^')
    {
        return stackPrecedence > currentPrecedence;
    }
    else
    {
        return stackPrecedence >= currentPrecedence;
    }
}

private int GetOperatorPrecedence(char op)
{
    return op switch
    {
        '+' or '-' => 1,
        '*' or '/' or '%' => 2,
        '^' => 3,
        _ => 0 // 括号等非运算符优先级最低
    };
}

2. 修正运算符栈弹出条件 #

将evaluate函数中处理运算符的循环条件替换为新的判断函数：

else if (c == '+' || c == '-' || c == '*' || c == '/' || c == '%' || c == '^')
{
    while (operatorStack.Count > 0 && ShouldPopStackOperator(c, operatorStack.Peek()))
    {
        outputQueue.Enqueue(operatorStack.Pop().ToString());
    }
    operatorStack.Push(c);
}

3. 补充右括号处理（可选） #

标准Shunting Yard算法需要处理右括号，将栈中运算符弹出直到遇到左括号。虽然当前递归处理括号的方式可行，但补充右括号处理可以让逻辑更完整（避免表达式末尾残留右括号的错误）：

else if (c == ')')
{
    // 弹出栈中运算符直到遇到左括号
    while (operatorStack.Count > 0 && operatorStack.Peek() != '(')
    {
        outputQueue.Enqueue(operatorStack.Pop().ToString());
    }
    // 弹出左括号（不加入输出队列）
    if (operatorStack.Count > 0)
    {
        operatorStack.Pop();
    }
    else
    {
        throw new Exception("Mismatched parentheses.");
    }
}

注意：如果保留递归处理括号的逻辑，此部分可忽略，但建议统一为标准Shunting Yard流程，避免递归带来的栈溢出风险（针对极深嵌套的表达式）。

验证修复 #

修复后，表达式5*2+(5*10)/5会生成正确的后缀表达式5 2 * 50 5 / +，计算流程为：

1. 5*2=10
2. 50/5=10
3. 10+10=20，得到正确结果。

内容的提问来源于stack exchange，提问作者ImNotPsychotic