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

/* 功能：四則運算

 * 輸入：strExpression：字符串格式的算術表達式，如: "3+2*{1+2*[-4/(8-6)+7]}"* 返回：算術表達式的計算結果*/public static int calculate(String strExpression){/* 請實現*/return 0;} 

約束：

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

2. pucExpression算術表達式的有效性由調用者保證;

預備知識

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

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

2. 后綴表達式
   后綴表達式就是運算符在運算數的而后面。它有什么特點嗎？我們先看個例子，還是以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;
}

總結

以上是生活随笔為你收集整理的经典笔试上机考题-表达式求值的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。