利用堆栈计算算数表达式

       用堆栈求算术表达式在数据结构中也是一个比较经典的问题，其主要原理就是利用两个堆栈，首先利用一个堆栈把算数表达式（中缀表达式，即我们常用的表达式）转换为后缀表达式，再利用另一个堆栈，把中缀表达式中的数字进行相关操作，最后栈里的值为所求结果，直接弹出即可。

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();
        }