具體的分析講解可以看我的博客如下
利用棧實(shí)現(xiàn)表達(dá)式講解鏈接
下面直接上代碼，具體的分析在代碼的注釋中了~我是用string實(shí)現(xiàn)的~
#include<bits/stdc++.h>using namespace std;stack<char>sign; //記錄符號(hào) queue<string>exchange; //記錄中綴式轉(zhuǎn)換為后綴式的輸出 stack<int>number; //以int形勢(shì)記錄后綴式計(jì)算時(shí)的值 int stackout(char c){ //棧外符號(hào)優(yōu)先級(jí)值 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){ //棧內(nèi)符號(hào)優(yōu)先級(jí)值 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型轉(zhuǎn)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=""; //記錄多位數(shù)的字符串 for(int i=0;i<s.size();i++){ if(s[i]>='0'&&s[i]<='9'){ //如果是字符，說明是數(shù)的一部分 tmp+=s[i]; } else { if(tmp!=""){ //必須有這個(gè)，因?yàn)榭赡艹霈F(xiàn)*(這種情況，這個(gè)時(shí)候tmp是空的 exchange.push(tmp); tmp=""; } if(s[i]=='('){ //如果是(入棧 sign.push(s[i]); } else if(s[i]==')'){ //如果是)一直出棧到(出現(xiàn) while(sign.top()!='('){ string zc=""; zc+=sign.top(); //char轉(zhuǎn)到string exchange.push(zc); sign.pop(); } sign.pop(); //彈出(，這個(gè)(是不出現(xiàn)在表達(dá)式中的 } else { if(sign.empty()){ //初始時(shí)如果棧是空的，不管是什么直接入棧 sign.push(s[i]); continue; } int sign1,sign2; sign1=stackout(s[i]); //計(jì)算當(dāng)前比較字符的棧外優(yōu)先級(jí)值 sign2=stackin(sign.top()); //計(jì)算棧頂比較字符的棧內(nèi)優(yōu)先級(jí)值 if(sign1<=sign2){ //當(dāng)棧外值較小時(shí) int sign3; string zc=""; //比較過了直接彈出記錄 zc+=sign.top(); exchange.push(zc); sign.pop(); while(!sign.empty()){ //繼續(xù)彈出記錄 sign3=stackin(sign.top()); if(sign3<=sign2) break; //直到出現(xiàn)大于棧頂操作符的優(yōu)先級(jí)結(jié)束，注意現(xiàn)在都是和棧頂比的！！！ zc.clear(); zc+=sign.top(); exchange.push(zc); sign.pop(); } sign.push(s[i]); //記著把棧外的入棧 } else{ sign.push(s[i]); //當(dāng)棧外的優(yōu)先級(jí)值大的時(shí)候直接入棧 } } } } if(tmp!=""){ //最后一個(gè)數(shù)進(jìn)入后綴表達(dá)式 exchange.push(tmp); } while(!sign.empty()){ //未彈出的符號(hào)進(jìn)入后綴表達(dá)式 string zc=""; zc+=sign.top(); exchange.push(zc); sign.pop(); } //計(jì)算后綴表達(dá)式了 while(!exchange.empty()){ tmp=exchange.front(); exchange.pop(); if(tmp[0]>='0'&&tmp[0]<='9'){ //是數(shù)字轉(zhuǎn)換后進(jìn)入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); //計(jì)算完了入棧 } } cout<<number.top()<<endl; //剩下的最后一個(gè)就是結(jié)果 }int main(){ //freopen("input.txt","r",stdin); string s; while(cin>>s){ calc(s); } return 0;}新聞熱點(diǎn)
疑難解答
圖片精選
網(wǎng)友關(guān)注
