利用堆棧計算算數表達式

       用堆棧求算術表達式在資料結構中也是一個比較經典的問題，其主要原理就是利用兩個堆棧，首先利用一個堆棧把算數表達式（中綴表達式，即我們常用的表達式）轉換為字尾表達式，再利用另一個堆棧，把中綴表達式中的數字進行相關操作，最後棧裡的值為所求結果，直接彈出即可。

private string MidExpression(string orgstr)
        {
            StringBuilder temp = new StringBuilder();
            foreach (var item in orgstr)
            {
                switch (item)
                {
                    case '(':
                        symbols.Push(item);
                        break;
                    case ')':
                        {
                            while (symbols.Count > 0)
                            {
                                if (symbols.Peek() != '(')
                                {
                                    temp.Append(symbols.Pop());
                                }
                                else
                                {
                                    symbols.Pop();
                                }
                            }
                        }
                        break;
                    case '+':
                        {
                            if (symbols.Count > 0)
                            {
                                char topchar = symbols.Peek();
                                if (topchar == '*' || topchar == '/' || topchar == '+' || topchar == '-')
                                {
                                    temp.Append(symbols.Pop());
                                    symbols.Push(item);
                                }
                                else
                                {
                                    symbols.Push(item);
                                }
                            }
                            else
                            {
                                symbols.Push(item);
                            }
                        }
                        break;
                    case '-':
                        {
                            if (symbols.Count > 0)
                            {
                                char topchar = symbols.Peek();
                                if (topchar == '*' || topchar == '/' || topchar == '+' || topchar == '-')
                                {
                                    temp.Append(symbols.Pop());
                                    symbols.Push(item);
                                }
                                else
                                {
                                    symbols.Push(item);
                                }
                            }
                            else
                            {
                                symbols.Push(item);
                            }
                        }
                        break;
                    case '*':
                        if (symbols.Count > 0)
                        {
                            char topchar = symbols.Peek();
                            if (topchar == '*' || topchar == '/')
                            {
                                temp.Append(symbols.Pop());
                                symbols.Push(item);
                            }
                            else
                            {
                                symbols.Push(item);
                            }
                        }
                        else
                        {
                            symbols.Push(item);
                        }

                        break;
                    case '/':
                        if (symbols.Count > 0)
                        {
                            char topchar = symbols.Peek();
                            if (topchar == '*' || topchar == '/')
                            {
                                temp.Append(symbols.Pop());
                                symbols.Push(item);
                            }
                            else
                            {
                                symbols.Push(item);
                            }
                        }
                        else
                        {
                            symbols.Push(item);
                        }
                        break;
                    default:
                        temp.Append(item);
                        break;
                }
            }
            while (symbols.Count > 0)
            {
                temp.Append(symbols.Pop());
            }

            return temp.ToString();
        }
           

       先把字元串轉為字尾表達式：原理就是從左往右依次讀取表達式的每個字元，如果為“（”直接入棧，如果是“）”，則依次出棧，直到遇到“（” (注意，出棧時直接把出棧結果拼接到字尾表達式中，但不拼接括号)，如果是數字，直接拼接到表達式中，如果為操作符（即+ - * /），用該操作符與棧頂的操作符比較，若優先級高于棧定操作符，則直接入棧，否則先出棧，再入棧。注意，此時隻判斷棧定操作符的優先級，如果為括号，則直接入棧。讀取完之後直接如果棧中還有操作符，則直接拼接到表達式中。

       根據字尾表達式求值。原理就是從左往右依次讀字尾表達式，如果為數字，直接入棧，如果為操作符，則彈出需要的操作數，計算完結果後再入棧。讀取完畢後棧中的值為表達式結果。

private int compute(string midstr)
        {
            foreach (var item in midstr)
            {
                switch (item)
                {
                    case '+':
                        int fp = numbers.Pop();
                        int sp = numbers.Pop();
                        numbers.Push(fp + sp);
                        break;
                    case '-':
                        int fs = numbers.Pop();
                        int ss = numbers.Pop();
                        numbers.Push(ss - fs);
                        break;
                    case '*':
                        int fx = numbers.Pop();
                        int sx = numbers.Pop();
                        numbers.Push(fx * sx);
                        break;
                    case '/':
                        int fd = numbers.Pop();
                        int sd = numbers.Pop();
                        numbers.Push(sd / fd);
                        break;
                    default:
                        numbers.Push(Convert.ToInt32(item.ToString()));
                        break;
                }
            }
            return numbers.Pop();
        }
           

測試調用

static void Main(string[] args)
        {
            string exp = "(((1+1)*3/2+1)-1)*2";
            StackClass myclsaa = new StackClass(exp);
            int result = myclsaa.OutPut();
            Console.WriteLine(result);
            Console.ReadLine();
        }