C++表達式求值詳解
一.細節處理:
1.註意負數 因此要進行字符串預處理
string format(string str) { int len = str.length(); for (int i = 0; i < len; i++) { if (str[i] == '-') { if (i == 0) { str.insert(0, 1, '0'); }//處理-3*2+1情況 else if (str[i - 1]=='(') { str.insert(i, 1, '0'); }//處理(-3*4+1)情況 } } return str; }
2.考慮除數為0
case '/': if (0 != y) { res = x / y; } else { cout << "非法表達式"; return -1; } break;
3.原字符串再加上一個定界符 ‘#’
str=str+'#'
4.優先級:
1.”(“未入棧前為3 入棧後為0 2.”)”和”#”為0 3.”+” “-“為1 4.”*”和”/”為2
二.知識要點:
中綴表達式轉為後綴表達式
1. 首先設置存儲運算符和存儲操作數兩個棧 即Symbol[N]和Num[N]且分別對應top2,top1
top1=-1 Symbol[0]='#' //運算符棧設置定界符 top2=0
2.入棧和出棧的規則 字符串為str
一.若str[i]>=’0&&str[i]<=’9′,則入操作數棧並繼續掃描以一個字符 即Num[++top1]=str[i++]-‘0’;
二.否則 將當前字符str1與運算符棧的棧頂元素str2進行優先級比較 ,自寫比較函數
例如: str1==‘+’ 則若str2==# ,(,) 則返回1 說明str1比str2優先級高
1. 此時若str1優先級大於str2 則將str1入運算符棧並繼續掃描 即 Symbol[++top2]=str[i++]
2.優先級相等則返回0 此時將運算符棧頂元素彈出,並繼續掃描下一個字符即 top2– i++
3.若str1優先級小於str2返回-1,此時將運算符棧頂元素彈出 即op=Symbol[top2–]
並彈出操作數棧的兩個元素 即y=Num[top1–],x=Num[top1–] 之後進行計算操作
三.最後 return Num[top1]
三.完整源碼:
#define _CRT_SECURE_NO_WARNINGS #include<bits/stdc++.h> using namespace std; class Expression { public: Expression(string str); ~Expression(); int Compute(); private: int Comp(char str1, char str2); string str1; }; Expression::Expression(string str) { this->str1 = str + '#';//以定界符開頭 } Expression :: ~Expression() {} //將中綴表達轉為後綴表達 int Expression::Compute() { int Num[100], Symbol[100];//定義存操作數和運算符的兩個棧 int i, k, x, y, res; char op; Symbol[0] = '#'; int top1 = -1, top2 = 0; for (i = 0; str1[i] != '\0';) { if (str1[i] >= '0' && str1[i] <= '9') { Num[++top1] = str1[i++] - '0'; } else {//非操作數就比較運算符優先級 int cmp = Comp(str1[i], Symbol[top2]); if (cmp == 1) { Symbol[++top2] = str1[i++]; }//將運算符入棧 並接著掃描下一個字符 else if (cmp == 0) { --top2; i++; }//優先級相等 彈棧 並接著掃描下一個字符 else {//優先級低 繼續處理當前運算符 y = Num[top1--];//後面的數要先彈出來 才不會算反 x= Num[top1--]; op = Symbol[top2--]; switch (op) { case '+': res = x + y;//將運算結果入棧 break; case '-': res = x - y; break; case '*': res = x * y; break; case '/': if (0 != y) { res = x / y; } else { cout << "非法表達式"; return -1; } break; default:break; } Num[++top1] = res; } } } return Num[top1]; } string format(string str) { int len = str.length(); for (int i = 0; i < len; i++) { if (str[i] == '-') { if (i == 0) { str.insert(0, 1, '0'); }//處理-3*2+1情況 else if (str[i - 1]=='(') { str.insert(i, 1, '0'); }//處理(-3*4+1)情況 } } return str; } int main() { string str; int n = 3; while (n--) { cout << "請輸入一個表達式: " << endl; cin >> str; str = format(str); Expression E(str); int result = E.Compute(); cout << "表達式的值的是: " << result << endl; } return 0; } int Expression::Comp(char str1, char str2)//當前字符元素和棧頂運算符優先級比較 { //1代表 str1優先級大於str2 0 代表相等 -1代表小於 switch (str1) { case'+':case'-': if (str2 == '#'||str2==')'||str2=='(') { return 1; }//左括號入隊列後優先級變為0 else { return -1; } break; case'*':case'/': if (str2 == '*' || str2 == '/') { return -1; } else { return 1; } break; case'(': return 1; break; case')': if (str2 == '(') { return 0; } else if(str2 == '#') { return 1; } else { return -1; } break; case'#': if (str2 == '#') { return 0; } else { return -1; } break; default: break; } }
四.測試結果:
總結
本篇文章就到這裡瞭,希望能夠給你帶來幫助,也希望您能夠多多關註WalkonNet的更多內容!