C#利用栈实现加减乘除运算

C#利用栈实现加减乘除运算攻略

背景

在程序设计中，实现加减乘除运算是非常基础和常见的需求。而在计算表达式时，我们可以利用栈的特性来进行运算，这样可以避免使用递归等复杂的算法。本篇文章将介绍如何使用C#语言利用栈实现加减乘除运算。

方案

1.利用栈实现加减运算

我们可以使用两个栈numStack和opStack，分别存放数字和操作符。具体的方法如下：

1.1. 遍历待计算的字符串，依次处理每一个字符。
1.2. 如果遇到数字，将其入数字栈numStack。
1.3. 如果遇到操作符，分两种情况处理：
1.3.1. 如果操作符栈opStack为空，则将操作符直接入栈。
1.3.2. 如果操作符不为空，比较当前操作符和操作符栈顶的优先级。如果当前操作符优先级不高于栈顶操作符，则从数字栈numStack中取出两个数进行运算，并将结果入栈numStack，重复此过程直到当前操作符优先级高于栈顶操作符或操作符栈为空，最后将当前操作符入栈opStack。
1.4.字符遍历结束后，如果操作符栈不为空，则依次取出操作符和数字进行运算。

下面是使用上述算法计算表达式(4+2)*5-3的演示(代码中用#表示空栈)：

numStack:   # 4  6  6  6  5  2  30  30  27
opStack:    # +  #  *  -  *  +   #   #   #

具体实现可以参考以下代码示例：

public static double Eval(string expr)
{
    var numStack = new Stack<double>();
    var opStack = new Stack<char>();
    for (int i = 0; i < expr.Length; i++)
    {
        if (char.IsDigit(expr[i]))
        {
            // 提取数字
            int j = i + 1;
            while (j < expr.Length && (char.IsDigit(expr[j]) || expr[j] == '.')) j++;
            numStack.Push(double.Parse(expr.Substring(i, j - i)));
            i = j - 1;
        }
        else
        {
            // 提取操作符
            char op = expr[i];
            while (opStack.Count > 0 && Priority(op) <= Priority(opStack.Peek()))
                numStack.Push(Compute(opStack.Pop(), numStack.Pop(), numStack.Pop()));
            opStack.Push(op);
        }
    }
    while (opStack.Count > 0)
        numStack.Push(Compute(opStack.Pop(), numStack.Pop(), numStack.Pop()));
    return numStack.Pop();
}

private static double Compute(char op, double a, double b)
{
    switch (op)
    {
        case '+': return b + a;
        case '-': return b - a;
        case '*': return b * a;
        case '/': return b / a;
        default: throw new ArgumentException($"Invalid operator \"{op}\".");
    }
}

private static int Priority(char op)
{
    switch (op)
    {
        case '+':
        case '-': return 1;
        case '*':
        case '/': return 2;
        default: throw new ArgumentException($"Invalid operator \"{op}\".");
    }
}

1.2. 利用栈实现加减乘除运算

在进行加减运算时，我们已经使用了栈来处理。接下来我们将介绍如何利用栈实现乘除运算的处理。具体的方法如下：

1.2.1. 遍历待计算的字符串，依次处理每一个字符。
1.2.2. 如果遇到数字，将其入数字栈numStack。
1.2.3. 如果遇到乘或除操作符，取出数字栈numStack的栈顶元素a，并再次取出数字栈numStack的栈顶元素b，计算b与a的乘(或除)积，并将结果压入数字栈numStack。
1.2.4. 如果遇到加或减操作符，则先将其入操作符栈opStack。

下面是使用上述算法计算表达式(4+2)*5/3的演示(代码中用#表示空栈)：

numStack:   # 4  6 30  10  3.33333333333333
opStack:    # +  #  *   /   #

具体实现可以参考以下代码示例：

public static double Eval(string expr)
{
    var numStack = new Stack<double>();
    var opStack = new Stack<char>();
    for (int i = 0; i < expr.Length; i++)
    {
        if (char.IsDigit(expr[i]))
        {
            // 提取数字
            int j = i + 1;
            while (j < expr.Length && (char.IsDigit(expr[j]) || expr[j] == '.')) j++;
            numStack.Push(double.Parse(expr.Substring(i, j - i)));
            i = j - 1;
        }
        else if (expr[i] == '*' || expr[i] == '/')
        {
            // 计算乘(或除)积
            double a = numStack.Pop();
            double b = numStack.Pop();
            numStack.Push(Compute(expr[i], a, b));
        }
        else if (expr[i] == '+' || expr[i] == '-')
        {
            // 入操作符栈
            opStack.Push(expr[i]);
        }
    }
    while (opStack.Count > 0)
    {
        char op = opStack.Pop();
        double a = numStack.Pop();
        double b = numStack.Pop();
        numStack.Push(Compute(op, a, b));
    }
    return numStack.Pop();
}

private static double Compute(char op, double a, double b)
{
    switch (op)
    {
        case '+': return b + a;
        case '-': return b - a;
        case '*': return b * a;
        case '/': return b / a;
        default: throw new ArgumentException($"Invalid operator \"{op}\".");
    }
}

结论

利用栈实现加减乘除运算，不仅比递归等算法容易理解，而且还可以避免出现栈溢出等问题，因此在程序设计中非常实用。本篇文章给出了两种实现方法，读者可以根据实际需求选择适合的方法。