## 引言

上文[编码技巧 --- 同步锁对象的选定](url)中，提到了在C#中，让线程同步有两种方式：

- 锁（lock、Monitor等）
- 信号量（EventWaitHandle、Semaphore、Mutex）

加锁是最常用的线程同步的方法，就不再讨论，本篇主要讨论使用信号量同步线程。



## WaitHandle介绍

实际上，再C#中 `EventWaitHandle` 、 `Semaphore` 、 `Mutex` 都是抽象类 `WaitHandle` 的派生类，它提供了一组等待信号的方法和属性。如下图：

![image.png](https://niuery.com/static/img/06bc52bb2afd12a18ebda40a8bc58535.image.png)

主要包含静态方法 `SignalAndWait()`，`WaitAll()`，`WaitAny()`及一个虚方法`WaitOne()`。下面介绍一个这几个方法。

介绍这些方法之前，先简单介绍一下 `WaitHandle` 的派生类 `EventWaitHandle`，该派生类有两个实现类 `AutoResetEvent` 和 `ManualResetEvent`，其方法列表如下：
![image.png](https://niuery.com/static/img/d536d928b78688801d1cf8b167531da4.image.png)

重点说一下，`Set()`和`Reset()`:

- Set()方法设置事件为有信号状态：当调用 `Set()` 时，它将被设置为终止状态，并允许一个或多个等待该事件的线程继续执行。
- Reset()方法设置事件为无信号状态：当调用 `Reset()` 时，它将被设置为非终止状态，所有想要等待该事件的线程都将被阻塞，直到调用 `Set()` 方法使其变为终止状态。

**注意：这里的有信号，无信号的意思类似于红绿灯，有信号你才能够通行，对于线程来说，有信号意味着可以接着往下运行，无信号则阻塞等待信号。**

接下来的代码段演示皆使用 `AutoResetEvent` 进行演示。

### SignalAndWait()

当调用 `WaitHandle` 的静态方法 `SignalAndWait()` 时，会使得当前线程等待一个 `WaitHandle` 对象的信号，同时设置另一个 `WaitHandle` 对象为有信号状态。当第一个 `WaitHandle` 对象收到信号时，当前线程继续执行，同时第二个 `WaitHandle` 对象变为无信号状态。

```csharp
static AutoResetEvent event1 = new AutoResetEvent(false);
static AutoResetEvent event2 = new AutoResetEvent(false);

static void Main(string[] args)
{
    Thread t1 = new Thread(new ThreadStart(Worker1));
    Thread t2 = new Thread(new ThreadStart(Worker2));

    t1.Start();
    t2.Start();

    Console.ReadLine();
}

static void Worker1()
{
    Console.WriteLine("线程1开始执行……");

    event1.WaitOne(); // 等待事件1的发生

    Console.WriteLine("线程1收到事件1的信号，继续执行……");

    WaitHandle.SignalAndWait(event1, event2); // 发送事件2的信号并等待事件2的发生

    Console.WriteLine("线程1收到事件2的信号，继续执行……");
}

static void Worker2()
{
    Console.WriteLine("线程2开始执行……");

    Thread.Sleep(2000); // 模拟线程2的执行时间

    Console.WriteLine("线程2发出事件1的信号……");

    event1.Set(); // 发送事件1的信号

    Thread.Sleep(2000); // 模拟线程2的执行时间

    Console.WriteLine("线程2发出事件2的信号……");

    WaitHandle.SignalAndWait(event2, event1); // 发送事件1的信号并等待事件1的发生

    Console.WriteLine("线程2收到事件1的信号，继续执行……");
}
```
输出：

```csharp
线程1开始执行……
线程2开始执行……
线程2发出事件1的信号……
线程1收到事件1的信号，继续执行……
线程2发出事件2的信号……
线程2收到事件1的信号，继续执行……
线程1收到事件2的信号，继续执行……
```
### WaitAll()

当调用 `WaitHandle` 的静态方法 `WaitAll()` 时，它可以等待多个WaitHandle对象的信号，直到所有对象都收到信号或等待超时。

```csharp
static AutoResetEvent[] events = new AutoResetEvent[3]
{
    new AutoResetEvent(false),
    new AutoResetEvent(false),
    new AutoResetEvent(false)
};

static void Main(string[] args)
{
    Thread t1 = new Thread(new ThreadStart(Worker1));
    Thread t2 = new Thread(new ThreadStart(Worker2));

    t1.Start();
    t2.Start();

    Console.ReadLine();
}

static void Worker1()
{
    Console.WriteLine("线程1开始执行……");

    WaitHandle.WaitAll(events); // 等待所有事件的发生

    Console.WriteLine("线程1收到所有事件的信号，继续执行……");
}

static void Worker2()
{
    Console.WriteLine("线程2开始执行……");

    Thread.Sleep(2000); // 模拟线程2的执行时间

    Console.WriteLine("线程2发出事件1的信号……");

    events[0].Set(); // 发送事件1的信号

    Thread.Sleep(2000); // 模拟线程2的执行时间

    Console.WriteLine("线程2发出事件2的信号……");

    events[1].Set(); // 发送事件2的信号

    Thread.Sleep(2000); // 模拟线程2的执行时间

    Console.WriteLine("线程2发出事件3的信号……");

    events[2].Set(); // 发送事件3的信号
}
```
输出：

```csharp
线程1开始执行……
线程2开始执行……
线程2发出事件1的信号……
线程2发出事件2的信号……
线程2发出事件3的信号……
线程1收到所有事件的信号，继续执行……
```
### WaitAny()

当调用 `WaitHandle` 的静态方法 `WaitAny()` 时，它可以等待多个WaitHandle对象中的任意一个对象收到信号，直到有一个对象收到信号或等待超时。

```csharp
static AutoResetEvent[] events = new AutoResetEvent[3]
{
    new AutoResetEvent(false),
    new AutoResetEvent(false),
    new AutoResetEvent(false)
};

static void Main(string[] args)
{
    Thread t1 = new Thread(new ThreadStart(Worker1));
    Thread t2 = new Thread(new ThreadStart(Worker2));

    t1.Start();
    t2.Start();

    Console.ReadLine();
}

static void Worker1()
{
    Console.WriteLine("线程1开始执行……");

    WaitHandle.WaitAny(events); // 等待任意事件的发生

    Console.WriteLine("线程1收到任意事件的信号，继续执行……");
}

static void Worker2()
{
    Console.WriteLine("线程2开始执行……");

    var randomIndex = new Random().Next(0, 2);

    Console.WriteLine("线程2发出任意一个事件的信号……");

    events[randomIndex].Set(); //发送任意一个事件的信号
}

```
输出：

```csharp
线程1开始执行……
线程2开始执行……
线程2发出任意一个事件的信号……
线程1收到任意事件的信号，继续执行……
```
### WaitOne()

`WaitOne()`方法上文中其实已经用到了，它就表示阻塞当前线程，等待当前 `WaitHandle` 对象收到信号，直到对象收到信号或等待超时。如果WaitHandle对象收到信号，WaitOne()方法返回true，否则返回false。使用简单就不在贴代码段。

## 派生类的异同

上面已经提到了`EventWaitHandle` 、 `Semaphore` 、 `Mutex` 都是抽象类 `WaitHandle` 的派生类，它们的作用类似，但在使用和实现上有一些不同。下面我们来简单介绍下它们的异同点。

1. EventWaitHandle：

    `EventWaitHandle` 有两种类型：`AutoResetEvent` 和 `ManualResetEvent`。它们的区别在于`AutoResetEvent` 在有信号时只通知一个等待线程，而 `ManualResetEvent` 在有信号时通知所有等待线程。
两者设置为终止状态的方式都是调用 `Set()` 方法。
2. Semaphore

    `Semaphore` 可以用于多个线程之间的资源控制。`Semaphore` 可以控制同时访问共享资源的线程数量。设置为终止状态的方式是调用 `Release()` 方法。
3. Mutex

    `Mutex` 可以用于多个线程之间的互斥访问共享资源。`Mutex` 可以保证同一时间只有一个线程可以访问共享资源。设置为终止状态的方式是调用 `ReleaseMutex()` 方法。

并发编程 --- 信号量线程同步

## 引言

众所周知，使用线程可以极大的提高应用程序的效率和响应性，提高用户体验，但是不可以无节制的使用线程，为什么呢？



## 线程的开销
线程的开销实际上是非常大的，我们从空间开销和时间开销上分别讨论。

### 线程的空间开销
线程的空间开销来自这四个部分：
1. 线程内核对象(Thread Kernel Object)。每个线程都会创建一个这样的对象，它主要包含线程上下文信息，在32位系统中，它所占用的内存在700字节左右。
2. 线程环境块(Thread Environment Block)。TEB包括线程的异常处理链，32位系统中占用4KB内存。
3. 用户模式栈(User Mode Stack),即线程栈。线程栈用于保存方法的参数、局部变量和返回值。每个线程栈占用1024KB的内存。要用完这些内存很简单，写一个不能结束的递归方法，让方法参数和返回值不停地消耗内存，很快就会发生 `OutOfMemoryException` 。
4. 内核模式栈(Kernel Mode Stack)。当调用操作系统的内核模式函数时，系统会将函数参数从用户模式栈复制到内核模式栈。在32位系统中，内核模式栈会占用12KB内存。
### 线程的时间开销
线程的时间开销来自这三个过程：
1. 线程创建的时候，系统相继初始化以上这些内存空间。
2. 接着CLR会调用所有加载DLL的DLLMain方法，并传递连接标志（线程终止的时候，也会调用DLL的DLLMain方法，并传递分离标志)。
3. 线程上下文切换。一个系统中会加载很多的进程，而一个进程又包含若干个线程。但是一个CPU内核在任何时候都只能有一个线程在执行。为了让每个线程看上去都在运行，系统会不断地切换“线程上下文”：每个线程及其短暂的执行时间片，然后就会切换到下一个线程了。
    
    这个线程上下文切换过程大概又分为以下5个步骤：
    - 步骤1进入内核模式。
    - 步骤2将上下文信息（主要是一些CPU寄存器信息）保存到正在执行的线程内核对象上。
    - 步骤3系统获取一个 `Spinlock` ，并确定下一个要执行的线程，然后释放 `Spinlock` 。如果下一个线程不在同一个进程内，则需要进行虚拟地址交换。
    - 步骤4从将被执行的线程内核对象上载入上下文信息。
    - 步骤5离开内核模式。


所以，由于要进行如此多的工作，所以创建和销毁一个线程就意味着代价“昂贵”，即使现在的CPU多核多线程，如无节制的使用线程，依旧会严重影响性能。

## 引入线程池

为了免程序员无节制地使用线程，微软开发了“线程池”技术。简单来说，线程池就是替开发人员管理工作线程。当一项工作完毕时，CLR不会销毁这个线程，而是会保留这个线程一段时间，看是否有别的工作需要这个线程。至于何时销毁或新起线程，由CLR根据自身的算法来做这个决定。

线程池技术能让我们重点关注业务的实现，而不是线程的性能测试。

微软除实现了线程池外，还需要关注一个类型：`BackgroundWorker`。 `BackgroundWorker` 是在内部使用了线程池的技术：同时，在WinForm或WPF编码中，它还给工作线程和UI线程提供了交互的能力。

实际上， `Thread` 和 `ThreadPool` 默认都没有提供这种交互能力，而 `BackgroundWorker` 却通过事件提供了这种能力。这种能力包括：报告进度、支持完成回调、取消任务、暂停任务等。

`BackgroundWorker` 的简单示例如下：

```csharp
private BackgroundWorker backgroundWorker = new BackgroundWorker();

private void AsyncButton_Click(object sender, RoutedEventArgs e)
{
    //注册要执行的任务
    backgroundWorker.DoWork += BackgroundWorker_DoWork;
    //注册报告进度
    backgroundWorker.ProgressChanged += BackgroundWorker_ProgressChanged;
    //注册完成时的回调
    backgroundWorker.RunWorkerCompleted += BackgroundWorker_RunWorkerCompleted;
    //设置允许任务取消
    backgroundWorker.WorkerSupportsCancellation = true;
    //设置允许报告进度
    backgroundWorker.WorkerReportsProgress = true;
    backgroundWorker.RunWorkerAsync();
}
private void Cancel_Click(object sender, RoutedEventArgs e)
{
    //取消任务
    if (backgroundWorker.IsBusy)
        backgroundWorker.CancelAsync();
}
private void BackgroundWorker_RunWorkerCompleted(object? sender, RunWorkerCompletedEventArgs e)
{
    //完成时回调
    MessageBox.Show("BackgroundWorker RunWorkerCompleted");
}

private void BackgroundWorker_ProgressChanged(object? sender, ProgressChangedEventArgs e)
{   
    //报告进度
    this.textbox.Text = e.ProgressPercentage.ToString();
}

private void BackgroundWorker_DoWork(object? sender, DoWorkEventArgs e)
{
    BackgroundWorker? worker = sender as BackgroundWorker;

    if (worker != null)
    {
        for (int i = 0; i < 20; i++)
        {
            if (worker.CancellationPending)
            {
                e.Cancel = true;
                break;
            }
            worker.ReportProgress(i);

            Thread.Sleep(100);
        }
    }
}
```

建议使用WinForm和WPF的开发人员使用 `BackgroundWorker`。

## Task替代ThreadPool

`ThreadPool` 相对于 `Thread` 来说具有很多优势，但是 `ThreadPool` 在使用上却存在一定的不方便。比如：
- `ThreadPool` 不支持线程的取消、完成、失败通知等交互性操作。
- `ThreadPool` 不支持线程执行的先后次序。

所以随着 `Task` 类及其所提供的异步编程模型的引入，`Task`相较`ThreadPool`具有更多的优势。大概有一下几点：


1. Task是.NET Framework的一部分，它提供了更高级别的抽象来表示异步操作或并发任务。相比之下，ThreadPool较为底层，需要手动管理线程池和任务队列。通过使用Task，我们可以以更简洁、更可读的方式表达并发逻辑，而无需关注底层线程管理的细节。


2. Task是基于Task Parallel Library（TPL）构建的核心组件，它提供了强大的异步编程支持。利用Task，我们能够轻松定义异步方法、等待异步操作完成以及处理任务结果。与此相反，ThreadPool主要用于执行委托或操作，缺乏直接的异步编程功能。
 
3. Task在底层使用ThreadPool来执行任务，但它提供了更优秀的性能和资源管理机制。通过使用Task，我们可以利用TPL提供的任务调度器，智能化地管理线程池的大小、工作窃取算法和任务优先级。这样一来，我们能够更有效地利用系统资源，并获得更好的性能表现。

 
4. Task拥有强大的任务关联和组合功能。我们可以使用Task的 `ContinueWith()` 、 `When()` 、`WhenAll()` 、`Wait()`等方法定义任务之间的依赖关系，以及在不同任务完成后执行的操作。这种任务组合方式使并发编程更加灵活且易于管理。


5. Task提供了更好的异常处理和取消支持机制。我们可以利用Task的异常处理机制捕获和处理任务中的异常，而不会导致整个应用程序崩溃。此外，Task还引入 `CancellationToken` 的概念，可用于取消任务的执行，从而更好地控制并发操作。

 
所以，尽管ThreadPool在某些情况下仍然有其用途，但在C#编程中，使用Task替代ThreadPool已变为通用实践，推荐优先考虑使用Task来处理并发任务。

>以上部分内容引用自
>
>编写高质量代码：改善C#程序的157个建议 / 陆敏技著.一北京：机械工业出版社，2011.9

并发编程 ---为何要线程池化

## 引言

在C#中，让线程同步有两种方式：
- 锁（lock、Monitor）
- 信号量（EventWaitHandle、Semaphore、Mutex）

线程锁的原理，就是锁住一个资源，使得应用程序在此刻只有一个线程访问该资源。通俗地讲，就是让多线程变成单线程。在C#中，可以将被锁定的资源理解成 `new` 出来的普通CLR对象。



## 如何选定

既然需要锁定的资源就是C#中的一个对象，我们就该仔细思考，到底什么样的对象能够成为一个锁对象（也叫同步对象）？

那么选择同步对象的时候，应当始终注意以下几点：

1. 同步对象在需要同步的多个线程中是可见的同一个对象。
2. 在非静态方法中，静态变量不应作为同步对象。
3. 值类型对象不能作为同步对象。
4. 避免将字符串作为同步对象。
5. 降低同步对象的可见性。

## 原因分析

接下来就探讨一下这五种情况。

**注意事项1：需要锁定的对象在多个线程中是可见的，而且是同一个对象。**

“可见的”这是显而易见的，如果对象不可见，就不能被锁定。

“同一个对象”，这也很容易理解，如果锁定的不是同一个对象，那又如何来同步两个对象呢？

虽然理解起来简单，但不见得我们在这上面就不会犯错误。

我们模拟一个必须使用到锁的场景：在遍历一个集合的过程中，同时在另外一个线程中删除集合中的某项。

下面这个例子中，如果没有 `lock` 语句，将会抛出异常`System.InvalidOperationException:“Collection was modified; enumeration operation may not execute.”`


```csharp
public partial class Form1 : Form
{
    public Form1()
    {
        InitializeComponent();
    }

    AutoResetEvent autoResetEvent = new AutoRe

    List<string> strings = new List<string>() 

    private void btn_StartThreads_Click(object
    {
        object syncObj = new object();

        Thread t1 = new Thread(() =>
        {
            //确保等待t2开始之后才运行下面的代码
            autoResetEvent.WaitOne();

            lock (syncObj)
            {
                foreach (var item in strings)
                {
                    Thread.Sleep(1000);
                }
            }
        });
        t1.IsBackground = false;

        t1.Start();

        Thread t2 = new Thread(() =>
        {
            autoResetEvent.Set();

            Thread.Sleep(1000);

            lock (syncObj)
            {
                strings.RemoveAt(1);
            }

        });
        t2.IsBackground = false;

        t2.Start();
    }
}
```

上述例子是 `Winform` 窗体应用程序，按钮的单击事件中演示该功能。对象 `syncObj` 对于线程 `t1` 和 `t2` 来说，在CLR中肯定是同一个对象。所以，上面的示例运行是没有问题的。

现在，我们将此示例重构。将实际的工作代码移到一个类型 `SampleClass` 中，该示例要在多个 `SampleClass` 实例间操作一个静态字段，如下所示：

```csharp
public partial class Form1 : Form
{
    public Form1()
    {
        InitializeComponent();
    }

    private void btn_StartThreads_Click(object sender, EventArgs e)
    {
        SampleClass sampleClass1 = new SampleClass();
        SampleClass sampleClass2 = new SampleClass();
        sampleClass1.StartT1();
        sampleClass2.StartT2();
    }
}

public class SampleClass
{
    public static AutoResetEvent autoResetEvent = new AutoResetEvent(false);

    static List<string> strings = new List<string>() { "str1", "str2", "str3" };

    object syncObj = new object();

    public void StartT1()
    {
        Thread t1 = new Thread(() =>
        {
            //确保等待t2开始之后才运行下面的代码
            autoResetEvent.WaitOne();

            lock (syncObj)
            {
                foreach (var item in strings)
                {
                    Thread.Sleep(1000);
                }
            }
        });
        t1.IsBackground = false;

        t1.Start();
    }
    public void StartT2()
    {
        Thread t2 = new Thread(() =>
        {
            autoResetEvent.Set();

            Thread.Sleep(1000);

            lock (syncObj)
            {
                strings.RemoveAt(1);
            }

        });
        t2.IsBackground = false;

        t2.Start();
    }
}
```
该例子运行起来就会抛出异常`System.InvalidOperationException:“Collection was modified; enumeration operation may not execute.”`

查看类型 `SampleClass` 的方法 `StartT1` 和 `StartT2` ,方法内部锁定的是 `SampleClass` 的实例变量 `syncObj` 。

实例变量意味着，每创建一个 `SampleClass` 的实例都会生成一个 `syncObj` 对象。

在本例中，调用者一共创建了两个 `SampleClass` 实例，继而分别调用：
```csharp
samplel.StartTl();
sample2.StartT2();
```
也就是说，以上代码锁定的是两个不同的 `syncObj` ，这等于完全没有达到两个线程锁定同一个对象的目的。

要修正以上错误，只要将 `syncObj` 变成 `static` 就可以了。

另外，思考一下 `lock(this)` ，我们同样不建议在代码中编写这样的代码。如果两个对象的实例分别执行了锁定的代码，实际锁定的也就会是两个对象，完全不能达到同步的目的。

**第二个注意事项：在非静态方法中，静态变量不应作为同步对象。**

上文说到，要修正第一个注意事项中的示例问题，需要将 `syncObj` 变成 `static`。这似乎和本注意事项有矛盾。事实上，第一个注意事项中的示例代码仅仅出于演示的目的，在实际应用中，我们非常不建议编写此类代码。

在编写多线程代码时，要遵循这样的一个原则：

**类型的静态方法应当保证线程安全，非静态方法不需实现线程安全。**

FCL中的绝大部分类都遵循了这个原则。

像上一个示例中，如果将 `syncObj` 变成 `static`，就相当于让非静态方法具备了线程安全性，这带来的一个问题是，如果应用程序中该类型存在多个实例，在遇到这个锁的时候，它们都会产生同步，而这可能不是开发者所愿意看到的。第二个注意事项实际也可以归纳到第一个注意事项中。

**第三个注意事项：值类型对象不能作为同步对象。**

值类型在传递到另一个线程的时候，会创建一个副本，这相当于每个线程锁定的也是两个对象。因此，值类型对象不能作为同步对象。
**第四个注意事项：锁定字符串是完全没有必要的，而且相当危险。**

这整个过程看上去和值类型正好相反。字符串在CLR中会被暂存到内存里，如果有两个变量被分配了相同内容的字符串，那么这两个引用会被指向同一块内存。所以，如果有两个地方同时使用了`lock(“abc”)` ，那么它们实际锁定的是同一个对象，这会导致整个应用程序被阻滞。

**第五个注意事项：降低同步对象的可见性。**

可见范围最广的一种同步对象是 `typeof(SampleClass)`。

`typeof()`方法所返回的结果（也就是类型的type)是`SampleClass` 的所有实例所共有的，即：所有实例的type都指向typeof方法的结果。

这样一来，如果我们 `lock(typeof(SampleClass)` ,当前应用程序中所有 `SampleClass` 的实例线程将会全部被同步。这样编码完全没有必要，而且这样的同步对象太开放了。

一般来说，同步对象也不应该是一个公共变量或属性。在FCL的早期版本中，一些常用的集合类型（如 `ArrayList` )提供了公共属性 `SyncRoot` ，让我们锁定以便进行一些线程安全的操作。

所以你一定会觉得我们刚才的结论不正确。其实不然，`ArrayList` 操作的大部分应用场景不涉及多线程同步，所以它的方法更多的是单线程应用场景。线程同步是一个非常耗时（低效）的操作。若 `ArrayList` 的所有非静态方法都要考虑线程安全，那么 `ArrayList` 完全可以将这个 `SyncRoot` 变成静态私有的。现在它将 `SyncRoot` 变为公开的，是让调用者自己去决定操作是否需要线程安全。

我们在编写代码时，除非有这样的要求，否则就应该始终考虑降低同步对象的可见性，将同步对象藏起来，只开放给自己或自己的子类就够了（需要开放给子类的情况其实也不多）。

>本篇内容引用自
>
>编写高质量代码：改善C#程序的157个建议 / 陆敏技著.一北京：机械工业出版社，2011.9

编码技巧 --- 同步锁对象的选定

## 引言

最近做一个配置的功能，需求是该配置项跟另一个整形配置项关联，具有一定的函数关系，例如有一个配置项是值为 `N` ，则另一配置 `F` 项满足函数关系$F=2/(N+1)$。这个函数关系是客户手动输入，只需要简单的四则运算，所以我们要做的就是判断四则运算表达式是否有效，且给定 `N` 的值，算出表达式的值。

如何快速判断一个四则运算公式字符串是否符合规则，且根据给定值计算出该公式的值？



## 双栈实现

实际上编译器就是利用了双栈实现了的表达式求值，其中一个栈用来保存操作数，另一个栈用来保存运算符。

从左向右遍历表达式，当遇到数字时，就将其直接压入操作数栈；当遇到运算符时，就将其与运算符栈的栈顶元素比较。

如果遇到的运算符比运算符栈顶的元素的优先级高，就将这个运算符压入栈；

如果遇到的运算符比运算符栈顶的元素的优先级低或两者相同，就从运算符栈顶取出运算符，在从操作数栈顶取两个操作数，然后进行计算，并把计算的得到的结果压入操作数栈，继续比较这个运算符与运算符栈顶的元素；

下图表示一个简单四则运算表达式 `3+5*8-6`的计算过程：

![image.png](https://niuery.com/static/img/179736aa50301d68ddf5995fcc6f3305.image.png)

代码实现可以大概简化可以分为以下步骤：

1. 定义运算符栈 `operatorStack` 和操作数栈 `operandStack` 。

2. 从左至右扫描表达式,遇到操作数时,直接将其推入操作数栈 `operandStack` 。

3. 遇到运算符时,比较其与运算符栈顶部运算符的优先级:

    - 如果该运算符的优先级高于或等于运算符栈顶部运算符,则将该运算符直接入栈 `operatorStack` 。

    - 如果该运算符的优先级低于运算符栈顶部运算符,则将运算符栈顶部的运算符出栈,从操作数栈中弹出两个操作数,计算结果后再入栈 `operandStack` ,重复此步骤直到运算符栈为空或遇到优先级高于或等于该运算符的栈顶运算符为止。

4. 遇到括号时:
    - 如果是左括号“(”,则直接入栈 `operatorStack` 。

    - 如果是右括号“)”,则将运算符栈栈顶的运算符出栈,从操作数栈中弹出两个操作数计算结果,重复此步骤直到遇到左括号为止,并将这一对括号从运算符栈中移除。

5. 重复步骤3和4,直到表达式的最右端。

6. 将运算符栈中剩余的所有运算符依次出栈,从操作数栈中弹出两个操作数,计算结果后入栈operandStack。

7. 操作数栈最终只剩一个操作数,这就是表达式的计算结果。

具体实现代码如下：

```csharp
class ExpressionEvaluator
{
    static Dictionary<char, int> PrecedenceDic = new Dictionary<char, int> {
            {'+', 1}, {'-', 1}, {'*', 2}, {'/', 2}, {'^', 3}
        };

    static Dictionary<char, Func<int, int, int>> OperatorsDic = new Dictionary<char, Func<int, int, int>> {
            {'+', (a, b) => a + b },
            {'-', (a, b) => a - b },
            {'*', (a, b) => a * b },
            {'/', (a, b) => a / b },
            {'^', (a, b) => (int)Math.Pow(a, b)}
        };

    public static bool EvaluateExpression(string expression, out double result)
    {
        result = 0;
        try
        {
            // 使用正则表达式验证四则运算表达式的有效性
            string pattern = @"^[-+*/^() x\d\s]+$";

            if (!Regex.IsMatch(expression, pattern))
            {
                return false;
            }
            //操作符栈
            Stack<char> operatorStack = new Stack<char>();
            //操作数栈
            Stack<int> operandStack = new Stack<int>();

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

                if (c == ' ') continue;

                if (char.IsDigit(c))
                {
                    //获取操作数
                    int operand = 0;
                    while (i < expression.Length && char.IsDigit(expression[i]))
                    {
                        operand = operand * 10 + (expression[i++] - '0');
                    }
                    i--;
                    operandStack.Push(operand);
                }
                else if (OperatorsDic.ContainsKey(c))
                {
                    while (operatorStack.Count > 0 &&
                        OperatorsDic[c] != null && operatorStack.Peek() != '(' &&
                        PrecedenceDic[operatorStack.Peek()] >= PrecedenceDic[c])
                    {
                        int b = operandStack.Pop();
                        int a = operandStack.Pop();
                        operandStack.Push(OperatorsDic[operatorStack.Pop()](a, b));
                    }
                    operatorStack.Push(c);
                }
                else if (c == '(')
                {
                    operatorStack.Push(c);
                }
                else if (c == ')')
                {
                    while (operatorStack.Peek() != '(')
                    {
                        int b = operandStack.Pop();
                        int a = operandStack.Pop();
                        operandStack.Push(OperatorsDic[operatorStack.Pop()](a, b));
                    }
                    operatorStack.Pop();
                }
            }

            while (operatorStack.Count > 0)
            {
                int b = operandStack.Pop();
                int a = operandStack.Pop();
                operandStack.Push(OperatorsDic[operatorStack.Pop()](a, b));
            }
            result = operandStack.Pop();

            return true;
        }
        catch (Exception)
        {
            return false;
        }
    }
}
```
那接下来测试一下代码，因为代码内只做了整形的计算，所以表达式也只用整形。

![image.png](https://niuery.com/static/img/6d1f76e804d309a034bce9010ed0254d.image.png)

## 官方API

实际上微软官方在 `System.Data` 库中 `DataTable.Compute(String, String)`方法实现了计算表达式，代码如下 

```csharp
using System;
using System.Data;
using System.Text.RegularExpressions;

public class ArithmeticExpressionEvaluator
{
    public static bool IsArithmeticExpression(int arg, string str, out double result)
    {
        result = 0;

        // 验证字符串是否包含有效的四则运算表达式
        if (!IsValidArithmeticExpression(str) || !str.ToLower().Contains("x".ToLower()))
        {
            return false;
        }

        // 将字符串中的变量x替换为传入的整数arg
        string expression = str.Replace("x", arg.ToString());

        // 计算并返回表达式的值
        try
        {
            return double.TryParse(new DataTable().Compute(expression, "").ToString(), out result);
        }
        catch
        {
            return false;
        }
    }

    private static bool IsValidArithmeticExpression(string str)
    {
        // 使用正则表达式验证四则运算表达式的有效性
        string pattern = @"^[-+*/() x\d\s]+$";
        return Regex.IsMatch(str, pattern);
    }
}
class Program
{
    public static void Main()
    {
        while (true)
        {
            string expression = Console.ReadLine();
            string arg = Console.ReadLine();

            if (ArithmeticExpressionEvaluator.IsArithmeticExpression(int.Parse(arg), expression, out double result))
            {
                Console.WriteLine($"The result of the arithmetic expression is: {result}");
            }
            else
            {
                Console.WriteLine("The input string is not a valid arithmetic expression.");
            }
        }
    }
}
```

测试结果：

![image.png](https://niuery.com/static/img/b30dfb2819c69f92a821d3e961767df8.image.png)

## 总结

刚开始拿到这个需求还是有点头疼的，想了很久的方案，突然想到之前看数据结构的书的时候，提到过栈在表达式求值中的应用，翻书看了一下，还是被这个实现方案惊艳到了，所以，还是需要多读多看多思考，才能在面对各种需求游刃有余，加油~

编码技巧 --- 如何实现字符串运算表达式的计算

## 引言

最近想把一些英文官方文档的资料翻译成中文，然后转化为Markdown文档，然后发现[百度通用翻译的API](https://fanyi-api.baidu.com/doc/21)有不错的免费额度，个人申请也能申请到高级版。这个额度足够个人的日常使用了。

![image.png](https://niuery.com/static/img/137ebde496e29359c97ed1b9cd904d03.image.png)

## 如何使用
如何使用通用翻译API？
- 使用您的百度账号登录[百度翻译开放平台](http://api.fanyi.baidu.com/)；
- 注册成为开发者，获得 APPID ；
- 进行开发者认证（如仅需标准版可跳过）；
- 开通通用翻译API服务：[开通链接](https://fanyi-api.baidu.com/choose)；
- 参考技术文档和 Demo 编写代码。

注册完毕后，就可以在百度开放翻译平台的管理控制台看到APPID和密钥，这样就可以通过直接调用翻译API了。

以下内容来自百度翻译开放平台官方文档：
### API地址

通用翻译API通过 HTTP 接口对外提供多语种互译服务。您只需要通过调用通用翻译API，传入待翻译的内容，并指定要翻译的源语言（支持源语言语种自动检测）和目标语言种类，就可以得到相应的翻译结果。

通用翻译API HTTPS 地址：

```js
https://fanyi-api.baidu.com/api/trans/vip/translate
```
### 输入参数
请求方式： 可使用 `GET` 或 `POST` 方式，如使用 `POST` 方式，`Content-Type` 请指定为：`application/x-www-form-urlencoded` 。

字符编码：统一采用 UTF-8 编码格式。

query 长度：为保证翻译质量，请将单次请求长度控制在 6000 bytes以内（汉字约为输入参数 2000 个）。

![image.png](https://niuery.com/static/img/2e0e2b3ba236443d9b1bece990d2a72f.image.png)

### 输出参数

返回的结果是json格式，包含以下字段：

![image.png](https://niuery.com/static/img/af97155a4e64c550548ef109d6864b3e.image.png)

### 错误码

当翻译结果无法正常返回时，请参考下表处理

![image.png](https://niuery.com/static/img/28f1830083ea908b460dc41a5f7651c4.image.png)


### 签名生成

**这里需要特别注意，签名生成容易出错！**。

签名生成分为两步：
1. 将请求参数中的 APPID(appid)， 翻译 query(q，注意为UTF-8编码)，随机数(salt)，以及平台分配的密钥(可在管理控制台查看) 按照 appid+q+salt+密钥的顺序拼接得到字符串 1。
2. 对字符串 1 做 MD5 ，得到 32 位小写的 sign（注意一定转小写）。

除此之外，需要注意以下几点：

- 待翻译文本（q）需为 UTF-8 编码；
- 在生成签名拼接 appid+q+salt+密钥 字符串时，q 不需要做 URL encode，在生成签名之后，发送 HTTP 请求之前才需要对要发送的待翻译文本字段 q 做 URL encode；
- 如遇到报 54001 签名错误，请检查您的签名生成方法是否正确，在对 sign 进行拼接和加密时，q 不需要做 URL encode，很多开发者遇到签名报错均是由于拼接 sign 前就做了 URL encode；
- 在生成签名后，发送 HTTP 请求时，如果将 query 拼接在URL上，需要对 query 做 URL encode。


## 控制台程序Demo

接下来根据自己需要，参考上文中的参数，编写C#控制台程序，测试调用API接口。

```csharp
using System;
using System.Net.Http;
using System.Security.Cryptography;
using System.Text;
using System.Threading.Tasks;
using System.Web;

class Program
{
    static async Task Main(string[] args)
    {
        while (true)
        {
            var originalText = Console.ReadLine();
            await Translate(originalText);
        }
    }

    static async Task Translate(string originalText)
    {
        string APP_ID = "*************";//您的APPID

        string SecretKey = "****************";//您的密钥

        Random random = new Random();

        string salt = random.Next(10000, 99999).ToString();
        // appid + q + salt + 密钥的MD5值
        string sign = MD5Encrypt(APP_ID + originalText + salt + SecretKey);
        // 将输入的字符串进行URL编码并构造HTTP请求URL
        string url = $"https://fanyi-api.baidu.com/api/trans/vip/translate?" +
                     $"q={HttpUtility.UrlEncode(originalText)}" +
                     $"&from=en" +
                     $"&to=zh" +
                     $"&appid={APP_ID}" +
                     $"&salt={salt}" +
                     $"&sign={sign}";

        try
        {
            using (HttpClient client = new HttpClient())
            {
                // 发送GET请求并获取响应内容
                HttpResponseMessage response = await client.GetAsync(url);
                
                string responseBody = await response.Content.ReadAsStringAsync();
                // 解析响应JSON并输出翻译结果
                dynamic result = Newtonsoft.Json.JsonConvert.DeserializeObject(responseBody);
                
                Console.WriteLine($"{originalText} 的中文翻译为：{result.trans_result[0].dst}");
            }
        }
        catch (HttpRequestException e)
        {
            Console.WriteLine($"发生HTTP请求错误： {e.Message}");
        }
    }
    
    public static string MD5Encrypt(string input)
    {
        byte[] inputBytes = Encoding.UTF8.GetBytes(input);

        using (MD5 md5 = MD5.Create())
        {
            byte[] hashBytes = md5.ComputeHash(inputBytes);
            
            return BitConverter.ToString(hashBytes).Replace("-", "").ToLower();
        }
    }
}
```
示例图：

![image.png](https://niuery.com/static/img/5c469b0bd61165a54d4d86ea15a9873b.image.png)