具體的分析講解可以看我的博客如下
利用棧實現表達式講解鏈接
下面直接上代碼，具體的分析在代碼的注釋中了~我是用string實現的~
#include<bits/stdc++.h>using namespace std;stack<char>sign; //記錄符號 queue<string>exchange; //記錄中綴式轉換為后綴式的輸出 stack<int>number; //以int形勢記錄后綴式計算時的值 int stackout(char c){ //棧外符號優先級值 if(c=='(') return 7; else if(c=='*'||c=='/') return 5; else if(c=='+'||c=='-') return 3; else if(c==')') return 1;}int stackin(char c){ //棧內符號優先級值 if(c=='(') return 1; else if(c=='*'||c=='/') return 5; else if(c=='+'||c=='-') return 3; else if(c==')') return 7;}int string_to_int(string s){ //string型轉int型 int ans=0; for(int i=0;i<s.size();i++){ ans=ans*10+(s[i]-'0'); } return ans;}int calc(string s){ string tmp=""; //記錄多位數的字符串 for(int i=0;i<s.size();i++){ if(s[i]>='0'&&s[i]<='9'){ //如果是字符，說明是數的一部分 tmp+=s[i]; } else { if(tmp!=""){ //必須有這個，因為可能出現*(這種情況，這個時候tmp是空的 exchange.push(tmp); tmp=""; } if(s[i]=='('){ //如果是(入棧 sign.push(s[i]); } else if(s[i]==')'){ //如果是)一直出棧到(出現 while(sign.top()!='('){ string zc=""; zc+=sign.top(); //char轉到string exchange.push(zc); sign.pop(); } sign.pop(); //彈出(，這個(是不出現在表達式中的 } else { if(sign.empty()){ //初始時如果棧是空的，不管是什么直接入棧 sign.push(s[i]); continue; } int sign1,sign2; sign1=stackout(s[i]); //計算當前比較字符的棧外優先級值 sign2=stackin(sign.top()); //計算棧頂比較字符的棧內優先級值 if(sign1<=sign2){ //當棧外值較小時 int sign3; string zc=""; //比較過了直接彈出記錄 zc+=sign.top(); exchange.push(zc); sign.pop(); while(!sign.empty()){ //繼續彈出記錄 sign3=stackin(sign.top()); if(sign3<=sign2) break; //直到出現大于棧頂操作符的優先級結束，注意現在都是和棧頂比的?。?！ zc.clear(); zc+=sign.top(); exchange.push(zc); sign.pop(); } sign.push(s[i]); //記著把棧外的入棧 } else{ sign.push(s[i]); //當棧外的優先級值大的時候直接入棧 } } } } if(tmp!=""){ //最后一個數進入后綴表達式 exchange.push(tmp); } while(!sign.empty()){ //未彈出的符號進入后綴表達式 string zc=""; zc+=sign.top(); exchange.push(zc); sign.pop(); } //計算后綴表達式了 while(!exchange.empty()){ tmp=exchange.front(); exchange.pop(); if(tmp[0]>='0'&&tmp[0]<='9'){ //是數字轉換后進入number中 number.push(string_to_int(tmp)); } else { int key,number1,number2; number2=number.top(); //注意number1和number2的順序！ number.pop(); number1=number.top(); number.pop(); if(tmp=="+") key=number1+number2; if(tmp=="-") key=number1-number2; if(tmp=="*") key=number1*number2; if(tmp=="/") key=number1/number2; number.push(key); //計算完了入棧 } } cout<<number.top()<<endl; //剩下的最后一個就是結果 }int main(){ //freopen("input.txt","r",stdin); string s; while(cin>>s){ calc(s); } return 0;}新聞熱點
疑難解答
