經典筆試上機考題-表達式求值

相信參加過筆試面試同學應當見到過表達式求值這道題，下面下麪列舉的一道經典的考題，本文將同大家一起細細探討一下表達式求值這一類問題的求法，希望拋磚引玉，其中有不妥的地方也請大家多多批評指正。

/* 功能：四則運算
 * 輸入：strExpression：字串格式的算術表達式，如: "3+2*{1+2*[-4/(8-6)+7]}"

     * 返回：算術表達式的計算結果

 */

public static int calculate(String strExpression)

{

    /* 請實現*/

    return 0;

} 
約束：

pucExpression字串中的有效字元包括[‘0’-‘9’],‘+’,‘-’, ‘*’,‘/’ ,‘(’， ‘)’,‘[’,
‘]’,‘{’ ,‘}’。

pucExpression算術表達式的有效性由呼叫者保證;

預備知識

中綴表達式
我們常見的算術表達式，3*3，它的特點是運算子在數的中間，我們稱這類算術表達式爲中綴表達式。中綴表達式很符合我們人類的思維習慣，但對於機器運算來講，卻不是太明朗。這是因爲算術運算是有運算優先順序的，先乘除，後加減；先括號內的，在括號外；相同優先順序下從左到右。

5+6/2-34
它的正確理解應該是： 5 + 6/2-34=5+3-34=8-34=8-12=-4

後綴表達式
後綴表達式就是運算子在運算數的而後面。它有什麼特點嗎？我們先看個例子，還是以1）爲例，將它轉化爲後綴表達式形式

562/+34*-

怎麼理解呢？它的解讀：從左到右依次讀取，遇到數位放起來，遇到運算子就從數位裏面提取兩個進行運算，比如例子裏面的，62/就是6/2算完後更新到數據結構立面這樣數據就爲53，這樣繼續讀取+，再從數據裏面取出兩個運算，這樣繼續下去，最後數據結構裏面剩餘的就是最後的運算結果。很明顯這裏面用到的數據結構，具有後進先出的特性，棧就有這個性質。

解法

熟悉了上面提到的兩個概念後，對題目我們應該有了一個大概的解決策略了，但先別急於寫程式碼，我們再來看看題目。

通過上一節分析，我們知道解決這道題可以分兩步先變中綴表達式爲後綴表達式再對後綴表達式求值
題目裏面除了±*/四則運算外，還有三種不同類型的括號，別害怕，無論再多的括號型別，我們都明白一個點，他們有一個共同的特性，括號內的表達式要優先運算。可以這樣理解爲如果把左括號入棧的話，讀到對應的右括號，那麼需要將棧內左括號之後入棧的運算子全拋出來進行運算。
注意到運算數是有負數的，怎麼判斷？
先看看怎麼從字元流裏面把運算數給提取出來吧，順序讀取字元，直到非數位，然後將這幾個字元組成的字串轉成數位。怎麼判斷是負數？我的方法是增加一個變數儲存上次讀到的字元，然後判斷前一個不是數位的話，就認爲這個符號-是標識負數的意思。

到此我們整個的解題過程就比較明朗了，下面下麪將給出完整的實現程式碼，注意具體實現的時候並沒有講過程分爲明顯的兩步，而是用兩個棧來代替兩步過程，實現一遍讀取一遍運算。有喜歡的話，可以自行拆分成兩步分，這樣可能更好理解。

#include <iostream>
#include <stack>
using namespace std;

bool compare(char v1, char v2)
{
    if( v2 == '(' || v2 == '[' || v2 == '{')    return true;
    if( (v1 == '*' || v1 == '/' ) && (v2 == '+' || v2 == '-'))
        return true;    
    return false;
}

void caling(char c, stack<int>& q)
{
    int v1 = q.top();
    q.pop();
    int v2 = q.top();
    q.pop();
    switch(c)
    {
        case '+':
            q.push(v1+v2);
            break;
        case '-':
            q.push(v2 -v1);
            break;
        case '*':
            q.push(v1*v2);
            break;
        case '/':
            q.push(v2/v1);
            break;
    }
}

char matching(char c)
{
    if( c == ')') return '(';
    if(c == ']') return '[';
    return '{';
}

/* 功能：四則運算
* 輸入：strExpression：字串格式的算術表達式，如: "3+2*{1+2*[-4/(8-6)+7]}"
* 返回：算術表達式的計算結果
*/
int calculate(string strExpression)
{
    const char* p = strExpression.c_str();
    stack<char> s;
    stack<int> q;
    char last = ' ';
    string num;
            
    while(*p != '\0' )
    {
        switch(*p)
        {
            case '(':
            case '[':
            case '{':
                s.push(*p);
                break;
            case ')':               
            case ']':                
            case '}':
                while(s.top() != matching(*p))
                {
                    char c = s.top();
                    s.pop();
                    caling(c, q);                   
                }
                s.pop();           
                break;
            case '-':
                if(isdigit(last) == 0 && last != ')' && last != ']' && last != '}')
                {
                    p++;
                    int v = *p - '0';
                    v = 0-v;                    
                    q.push(v);
                    break;
                }
                if( s.empty() ) s.push(*p);
                else if( compare(*p, s.top())){
                        s.push(*p);
                }
                else
                {
                    while(s.size() >0 && !compare(*p, s.top()))
                    {
                        char c = s.top();
                        s.pop();
                        caling(c, q);
                    }
                    
                    s.push(*p);
                }       
                break;
            case '+':            
            case '*':
            case '/':
                if( s.empty() ) s.push(*p);
                else if( compare(*p, s.top())){
                    s.push(*p);
                }
                else
                {
                    while( s.size() >0 && !compare(*p, s.top()))
                    {
                        char c = s.top();
                        s.pop();
                        caling(c, q);
                    }
                    s.push(*p);
                }
                break;        
            default:
                num.clear();
                while(isdigit(*p) != 0)
                {
                    last = *p;
                    num.append(string(1,*p++));
                }
                q.push(std::atoi(num.c_str()));
                continue;                
        }
        last = *p;
        ++p;        
    }   

    while(!s.empty())
    {
        char c = s.top();
        s.pop();
        caling(c, q);                   
    }
    return q.top();
}

int main()
{
    string exp;
    while(cin>>exp)
    {
        cout<<calculate(exp)<<endl;
    }
    return 0;
}