今天看CSDN上有人问如何计算算数表达式的结果，比如"(2+3)*6"

原帖见：http://topic.csdn.net/u/20080731/11/50de3417-53d4-4228-99e6-505f64f8edde.html?seed=1989390904

我的算法是利用后缀表达式进行计算。后缀表达式的好处是在O(N)时间内完成表达式计算。

比如 "(2+3)*6"  转换为 " 2 3 + 6 * "

如果不清楚什么是后缀表达式，我就无语了。

得到后续表达式后，就是一个顺序压入堆栈执行的问题了

比如先获取第一个2入堆栈 ，然后是3入堆栈，然后发现是运算符+，这时执行运算符+，将2和3弹出，相加后入堆栈，然后是6，6入堆栈，然后是*，执行*，将堆栈中的两个数弹出执行，得到最后结果。

下面代码是我用BCB写的中缀转后缀表达式代码。图省事用了AnsiString，有空改成String就通用了。

//---------------------------------------------------------------------------
bool __fastcall IsOpertator(char aChar)
{
    switch(aChar)
    {
        case '+':
        case '-':
        case '*':
        case '/':
        case '(':
        case ')':
            return true;
        default:
            return false;
    }
}

int __fastcall OperatorLevel(char Opt)
{
    switch(Opt)
    {
        case '*':
            return 2;
        case '/':
            return 2;
        case '(':
            return 99;
        case ')':
            return 0;
        case '+':
            return 1;
        case '-':
            return 1;
        default:
            return 0;
    }
}

AnsiString __fastcall InfixToPostFix(AnsiString inputString)
{
    vector<char> OperatorStack;
    AnsiString PostFixString;

    //将表达式改为后缀表达式
    AnsiString tmpNumber;
    for(int i=0;i<inputString.Length();i++)
    {
        char tmpChar = inputString.c_str()[i];
        if(IsOpertator(tmpChar)) // 如果是操作符或括号
        {
            if(tmpNumber.Length()>0) // 如果还有正在处理的数字，数字读取完整，入后缀队列。
                PostFixString += tmpNumber+" ";
            tmpNumber = "";

            if(tmpChar == ')') // 如果是闭括号，需要一直弹出到开括号
            {
                while(!OperatorStack.empty())
                {
                    char thePopOpt = OperatorStack.back();

                    if(thePopOpt == '(')
                    {
                        OperatorStack.pop_back();
                        break;
                    }
                    else
                    {
                        PostFixString += AnsiString(thePopOpt)+" ";
                        OperatorStack.pop_back();
                    }
                }
                continue; // continue for;
            }

            // 同操作符堆栈栈顶元素比较，如果优先级高，就入栈，否则直到弹出所有元素
            while(!OperatorStack.empty())
            {
                char thePopOpt = OperatorStack.back();

                if(OperatorLevel(thePopOpt)>OperatorLevel(tmpChar))
                {
                    if(thePopOpt=='(')
                    {
                        OperatorStack.push_back(tmpChar);
                        tmpChar = '\0';
                        break;
                    }
                    else
                    {
                        OperatorStack.pop_back();
                        PostFixString += AnsiString(thePopOpt)+" ";
                    }
                }
                else if(OperatorLevel(thePopOpt)==OperatorLevel(tmpChar))
                {
                    OperatorStack.pop_back();
                    PostFixString += AnsiString(thePopOpt)+" ";

                    OperatorStack.push_back(tmpChar);
                    tmpChar = '\0';
                    break;
                }
                else
                {
                    OperatorStack.push_back(tmpChar);
                    tmpChar = '\0';
                    break; // break while
                }
            } // end while

            if(tmpChar!='\0')
                OperatorStack.push_back(tmpChar);
        }
        else    // 如果是数字
        {
            tmpNumber += AnsiString(tmpChar);

            if(i == inputString.Length()-1)
            {
                PostFixString += AnsiString(tmpNumber)+" ";
                break;
            }
        }
    }
    //----end for

    while(!OperatorStack.empty())
    {
        PostFixString += AnsiString(OperatorStack.back())+" ";
        OperatorStack.pop_back();
    }

    return PostFixString;
}