您好,登錄后才能下訂單哦!
使用C++實現(xiàn)逆波蘭表達(dá)式?很多新手對此不是很清楚,為了幫助大家解決這個難題,下面小編將為大家詳細(xì)講解,有這方面需求的人可以來學(xué)習(xí)下,希望你能有所收獲。
代碼思路:
(1)首先對輸入的中綴表達(dá)式合法性進(jìn)行判斷,bool isStringLegal(const char* str); 函數(shù)實現(xiàn)。
(2)然后把中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式。
(3)根據(jù)后綴表達(dá)式求出結(jié)果,double getTheResult(vector<string> &vec);函數(shù)實現(xiàn)。
注意:表達(dá)式的運(yùn)算符可以輸入 加、減、乘、除、括號,輸入的數(shù)據(jù)為整形數(shù)據(jù),計算結(jié)果為double型數(shù)據(jù)。
#include <iostream> #include <math.h> #include <map> #include <vector> #include <string.h> #include <memory> #include <string> #include <stdio.h> #include <stack> #include <stdlib.h> using namespace std; #define MAX_STRING_LENGTH 100 /* 解析當(dāng)前的整形數(shù)據(jù),并把整形數(shù)據(jù)轉(zhuǎn)換為string型 */ string analyData(const char* str, int &i); /* 根據(jù)逆波蘭表達(dá)式求表達(dá)式的值 */ double getTheResult(vector<string> &vec); /* 判斷該字符是否是 + - * / ( ) */ bool isCalChar(const char ch); /* 判斷輸入的中綴表達(dá)式是否合法 */ bool isStringLegal(const char* str); /* 解析當(dāng)前的整形數(shù)據(jù),并把整形數(shù)據(jù)轉(zhuǎn)換為string型 */ string analyData(const char* str, int &i) { int temp = i++; while(str[i] >= '0' && str[i] <= '9' && str[i] != '\0') { i++; } string s(str+temp,str+i); return s; } /* 根據(jù)逆波蘭表達(dá)式求表達(dá)式的值 */ double getTheResult(vector<string> &vec) { vector<string>::iterator it; stack<double> sta; string strTemp; double d = 0, d1 = 0, d2 = 0; for(it = vec.begin(); it != vec.end(); it++) { strTemp = (*it); if(strTemp == "+") { d1 = sta.top(); sta.pop(); d2 = sta.top(); sta.pop(); d = d1 + d2; sta.push(d); } else if(strTemp == "-") { d1 = sta.top(); sta.pop(); d2 = sta.top(); sta.pop(); d = d2 - d1; sta.push(d); } else if(strTemp == "*") { d1 = sta.top(); sta.pop(); d2 = sta.top(); sta.pop(); d = d2 * d1; sta.push(d); } else if(strTemp == "/") { d1 = sta.top(); sta.pop(); d2 = sta.top(); sta.pop(); d = d2 / d1; sta.push(d); } else { const char *p = strTemp.c_str(); d = atoi(p); sta.push(d); } } return sta.top(); } /* 判斷該字符是否是 + - * / ( ) */ bool isCalChar(const char ch) { if(ch == '+' || ch == '-' || ch == '*' || ch == '/' || ch == '(' || ch == ')') { return true; } return false; } /* 判斷輸入的中綴表達(dá)式是否合法 */ bool isStringLegal(const char* str) { /* 判斷是否是空串 */ if(NULL == str) { return false; } int len = strlen(str); int i = 0; int flag = 0; /* 字符串的開頭和末尾是否是數(shù)字 */ if(str[0] > '9' || str[0] < '0' || str[len-1] > '9' || str[len-1] < '0') { return false; } for(i = 0; str[i] != '\0'; i++) { /* 是否有除了加減乘除括號之外的字符 */ if(isCalChar(str[i]) == false) { return false; } /* 判斷是否有兩個連續(xù)的符號 */ if(i < len-1 && isCalChar(str[i]) == true) { if(isCalChar(str[i+1]) == true) { return false; } } /* 判斷括號是否成對 */ if(str[i] == '(') { flag++; } else if(str[i] == ')') { flag--; } /* 判斷是否出現(xiàn) )( 這樣的情況 */ if(flag < 0) { return false; } } /* 判斷括號是否匹配 */ if(flag != 0) { return false; } return true; } int main(void) { char str[MAX_STRING_LENGTH] = {0}; int i = 0; string data; /* 存放運(yùn)算符表達(dá)式的棧 */ stack<char> oper_char; /* 存放后綴表達(dá)式 */ vector<string> post_str; /* 輸入中綴的表達(dá)式 */ gets(str); /* 判斷輸入的中綴表達(dá)式是否合法 */ if(isStringLegal(str) != true) { cout << "This expression is not legal." << endl; } else { /* 將中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式 */ for(i = 0; str[i] != '\0'; i++) { /* 如果該字符為數(shù)字,解析該數(shù)字,并壓入棧 */ if(str[i] >= '0' && str[i] <= '9') { data = analyData(str,i); post_str.push_back(data); i--; } else if(str[i] == '(') { oper_char.push(str[i]); } else if(str[i] == ')') { char chtemp[2] = {0}; chtemp[0] = oper_char.top(); while(chtemp[0] != '(') { string strtemp(chtemp); post_str.push_back(strtemp); oper_char.pop(); chtemp[0] = oper_char.top(); } oper_char.pop(); } else if(str[i] == '+' || str[i] == '-') { char chtemp[2] = {0}; /* 全部出棧,但是碰到 '('就要停止出棧 */ while(oper_char.size() != 0) { chtemp[0] = oper_char.top(); if(chtemp[0] == '(') { break; } oper_char.pop(); string strtemp(chtemp); post_str.push_back(strtemp); } /*將當(dāng)前的表達(dá)式符號入棧*/ oper_char.push(str[i]); } else if(str[i] == '*' || str[i] == '/') { char chtemp[2] = {0}; while(oper_char.size() != 0) { chtemp[0] = oper_char.top(); if(chtemp[0] == '(' || chtemp[0] == '+' || chtemp[0] == '-') { break; } else { oper_char.pop(); string strtemp(chtemp); post_str.push_back(strtemp); } } /*將當(dāng)前的表達(dá)式符號入棧*/ oper_char.push(str[i]); } } /* 存放表達(dá)式的棧可能還有數(shù)據(jù) */ while(!oper_char.empty()) { char chtemp[2] = {0}; chtemp[0] = oper_char.top(); oper_char.pop(); string strtemp(chtemp); post_str.push_back(strtemp); } /* 把逆波蘭表達(dá)式求值 */ cout << getTheResult(post_str) << endl; } return 0; }
看完上述內(nèi)容是否對您有幫助呢?如果還想對相關(guān)知識有進(jìn)一步的了解或閱讀更多相關(guān)文章,請關(guān)注億速云行業(yè)資訊頻道,感謝您對億速云的支持。
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點不代表本網(wǎng)站立場,如果涉及侵權(quán)請聯(lián)系站長郵箱:is@yisu.com進(jìn)行舉報,并提供相關(guān)證據(jù),一經(jīng)查實,將立刻刪除涉嫌侵權(quán)內(nèi)容。