逆波兰式篇（后缀表达式）

一、逆波兰表示法（Reverse Polish notation，RPN，或逆波兰记法），是一种数学表达式方式，在逆波兰记法中，所有操作符置于操作数的后面。也称为后缀表达式。

二、一般算法

将一个普通的中序表达式转换为逆波兰表达式的一般算法是：

1. 　首先构造一个运算符栈，此运算符在栈内遵循越往栈顶优先级越高的原则。
2. 　读入一个中缀表达式，为了方便起见，可在其最右端追加一个最低优先级运算符（如：#号）。（这样做的目的是，最后读入#号运算符时将运算符栈中所有运算符都输      　　出）。
3. 　从左至右扫描该中缀表达式，如果当前字符是数字，则分析到该数字串的结束，并将该数字串直接输出。
4. 　如果不是数字，该字符则是运算符，此时需比较该运算符与运算符栈顶运算符的优先关系：
5. 　　（1）、若该运算符优先级高于栈顶运算符优先级别（或栈为空），则直接将该运算符压入运算符栈中；
6. 　　（2）、若该运算符优先级小于或等于此运算符栈顶的运算符，则弹出栈顶运算符并输出，重复比较、输出，直到栈为空或该运算符优先级高于栈顶运算符，然后将该运算　　符入栈。
7. 　重复上述操作(3)-(4)直至扫描完整个简单算术表达式，确定所有字符都得到正确处理，输出结果便是中缀表达式转化为逆波兰表示的简单算术表达式。

三、举例说明

　　例如中缀表达式：9+(3-1) X 3+10+2，其实是我们人类所理解的四则表达运算式，现在我们将其转为机器方便识别的后缀表达式。

四、算法实现

namespace Eduii.Practice.StackDemo
{
    /*
     * 词汇：
     *  postfix expression 后缀表达式
     *  infix expression   中缀表达式
     *  prefix expression  前缀表达式 
     * 
     */

    /*
     *分析：
     *目前四则运算符包括:(、）、+、-、*、/、%
     * 优先级：
     *      1、* 、/、%
     *      2、+ 、-
     *      3、(
     *      4、）
     * 
     */

    /*
     *拓展： 
     *    1、字符串包含其他字符的判断
     *    2、四则运算非个位时
     *    3、包含小数点
     *    4、包含正负号
     *    5、......
     */

    /*
     *参考文档
     *  http://www.cnblogs.com/mygmh/archive/2012/10/06/2713362.html
     *  http://www.nowamagic.net/librarys/veda/detail/2307
     *  http://www.cnblogs.com/stay-foolish/archive/2012/04/25/2470590.html
     */

    /// <summary>
    /// 逆波兰式的算法实现
    /// </summary>
    public class RPExpression
    {
        /// <summary>
        ///  使用字符串存储
        /// </summary>
        /// <param name="infixExpression"></param>
        /// <returns></returns>
        /*
         *从左到右遍历中缀表达式的每个数字和符号，若是数字就输出，即成为后
         *缀表达式的一部分；若是符号，若为‘(’,直接压入操作栈，
         *若为其他字符则判断其与栈顶符号的优先级，是右括号或优先级低
         *于栈顶符号(乘除优先加减)则栈顶元素依次出栈并输出， 并将当前符号进栈，一直
         *到最终输出后缀表达式为止。 
         * 
         */
        public string Convert2PostfixExpWithString(string infixExpression)
        {
            //后缀表达式
            string postfixExp = string.Empty;
            //先处理空格
            if (string.IsNullOrWhiteSpace(infixExpression))
                return postfixExp;
            //去除空格
            infixExpression = infixExpression.Trim();
            //操作栈
            Stack<char> operatorStack = new Stack<char>();
            //四则表达式长度
            int length = infixExpression.Length;
            //临时存储字符
            char temp;
            //数字
            string digital = string.Empty;
            for (int i = 0; i < length; i++)
            {
                temp = infixExpression[i];
                bool isOperator = IsOperator(temp);
                if (isOperator)
                {
                    if (!string.IsNullOrWhiteSpace(digital))
                    {
                        postfixExp += string.Format("{0},", digital);
                        digital = string.Empty;
                    }
                    if (temp == '(')
                        operatorStack.Push(temp);
                    //判断是否为'('
                    else if (temp == ')')
                    {
                        //当为‘)’时，直接取出栈顶的元素，直到第一个'('为止
                        char topElement = operatorStack.Pop();  //返回栈顶元素当不将其移除
                        while (topElement != '(')
                        {
                            postfixExp += string.Format("{0},", topElement);
                            if (operatorStack.Count == 0)
                                break;
                            topElement = operatorStack.Pop();
                        }
                    }
                    else
                    {
                        //栈为空时直接插入当前运算符
                        if (operatorStack.Count == 0)
                            operatorStack.Push(temp);
                        //栈中存在操作符时要判断优先级
                        else
                        {
                            char topElement = operatorStack.Peek();
                            while (topElement != '#')
                            {
                                if (ComparePriority(temp, topElement) > 0)
                                {
                                    operatorStack.Push(temp);
                                    topElement = '#';
                                }
                                else
                                {
                                    //当前栈顶出栈
                                    postfixExp += string.Format("{0},", topElement);
                                    operatorStack.Pop();
                                    if (operatorStack.Count != 0)
                                        topElement = operatorStack.Peek();
                                    else
                                    {
                                        operatorStack.Push(temp);
                                        topElement = '#';
                                    }
                                }
                            }
                        }
                    }
                }
                else
                {
                    //数字拼接
                    digital += temp;
                    //直接输出数字
                    if (i == length - 1)
                    {
                        postfixExp += string.Format("{0},", digital);
                    }
                }
            }

            //输出所有的操作
            while (operatorStack.Count > 0)
            {
                postfixExp += string.Format("{0},", operatorStack.Pop());
            }
            return postfixExp;
        }



        //比较优先级
        private int ComparePriority(char ch1, char ch2)
        {
            int ch1Pri = GetPriority(ch1);
            int ch2Pri = GetPriority(ch2);
            return ch1Pri - ch2Pri;
        }

        //获得字符优先级
        private int GetPriority(char ch)
        {
            switch (ch)
            {
                case '(':
                    return -1;
                case '+':
                case '-':
                    return 0;
                case '*':
                case '/':
                case '%':
                    return 1;
                default:
                    throw new Exception("未定义操作符.");
            }
        }

        // 判断字符是否为操作符
        private bool IsOperator(char ch)
        {
            if (ch == '+' || ch == '-' || ch == '*' || ch == '/' || ch == '%' || ch == '(' || ch == ')')
                return true;
            return false;
        }

        /// <summary>
        /// 计算后缀表达式值
        /// </summary>
        /// <param name="expression"></param>
        /// <returns></returns>
        /*
         *从左到右遍历表达式的每个数字和符号，遇到是数字就进栈，遇到是符
         *号，就将处于栈顶两个数字出栈，进行运算，运算结果进栈， 一直到最终获得结果。 
         */
        public decimal CalculatePostfixExp(string expression)
        {
            if (string.IsNullOrWhiteSpace(expression))
                return 0;
            //清除空格
            expression = expression.Trim();
            //数据
            decimal digigtal = 0;
            //取得后缀表达式中的字符
            int i = 0;
            char topElement = expression[i];
            Stack<decimal> dataStack = new Stack<decimal>();
            while (topElement != '#')
            {
                if (topElement != ',')
                {
                    if (IsOperator(topElement))
                    {
                        //取出栈顶元素进行运算
                        decimal num1 = dataStack.Pop();
                        decimal num2 = dataStack.Pop();
                        decimal result = Calculate(num2, num1, topElement);
                        dataStack.Push(result);

                    }
                    else
                    {
                        int singleDigit = topElement - 48;
                        if (digigtal != 0)
                            digigtal = digigtal * 10 + singleDigit;
                        else
                            digigtal = singleDigit;
                    }
                }
                else
                {
                    if (digigtal != 0)
                    {
                        dataStack.Push(digigtal);
                        digigtal = 0;
                    }
                }
                if (i == expression.Length - 1)
                    break;
                i++;
                topElement = expression[i];
            }
            return dataStack.Pop();
        }

        //两数相加
        private decimal Calculate(decimal num1, decimal num2, char ope)
        {
            switch (ope)
            {
                case '+':
                    return num1 + num2;
                case '-':
                    return num1 - num2;
                case '*':
                    return num1 * num2;
                case '/':
                    return num1 / num2;
                default:
                    throw new ApplicationException("未定义的数据类型.");
            }
        }
    }
}