HDOJ 1237 簡單電腦（棧）

簡單電腦

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)

Total Submission(s): 14952    Accepted Submission(s): 5098

Problem Description 讀入一個隻包含 +, -, *, / 的非負整數計算表達式，計算該表達式的值。

Input 測試輸入包含若幹測試用例，每個測試用例占一行，每行不超過200個字元，整數和運算符之間用一個空格分隔。沒有非法表達式。當一行中隻有0時輸入結束，相應的結果不要輸出。

Output 對每個測試用例輸出1行，即該表達式的值，精确到小數點後2位。

Sample Input

1 + 2
4 + 2 * 5 - 7 / 11
0
        

Sample Output

3.00
13.36
        

Source 浙大計算機研究所學生複試上機考試-2006年  

Recommend JGShining   |   We have carefully selected several similar problems for you:   1230  1235  1236  1233  1232

思路：利用兩個棧，一個存double數字，一個存char運算符，比如 4 + 2 * 5 - 7 / 11 ，遇到空格略過，遇到字元型數字轉換成double數字并存棧，遇到運算符：  1. 要運算并清空兩棧的情況：是+或-（運算并清空） &&&&&是*或/，并且其前的運算符棧内符号為*或/，按優先級來說就應該先計算前一個*或/（運算）。  2.運算符先存入棧的情況：是 *或 /，并且其前的運算符棧内符号不為*或 /。别忘了最後的最後要清空棧。

清楚思想請看：http://blog.csdn.net/jinjide_ajin/article/details/47108889

AC代碼，有一些很需要注意的地方都标記上了：

#include<cstdio>
#include<cstring>
#include<stack>
using namespace std;
stack <double> num;//數字棧
stack <char> sta;//字元棧

double math(char c){//變量為識别的運算符
    double a,b;//結果
    a=num.top(); num.pop();
    b=num.top(); num.pop();
    switch(c){
        case '*': return b*a;
        case '/': return b/a;
        case '+': return b+a;
        case '-': return b-a;
    }//注意這裡 a,b 順序不能反
}//隻進行一次運算

int main(){
    char oper,str[210];
    int len,i;
    double nnum;
    memset(str,0,sizeof(str));
    while(gets(str)&&strcmp(str,"0")!=0){
        len=strlen(str);
        /********************** for *******************/
        for(i=0;i<len;i++){
            while(str[i]==' ') i++;  //略過空格

            /************下面為轉換數字**********/
            nnum=0;
            while(str[i]>='0'&&str[i]<='9'&&i<len){
                nnum=nnum*10+str[i]-'0';
                i++;
            } //将數字由char轉換為double
            num.push(nnum); //數字進棧

            /************下面為略過空格**********/
            while(str[i]==' ') i++;//略過空格

            /************下面為判斷操作符**********/
            if(str[i]=='+'||str[i]=='-'){
                while(!sta.empty()){
                    num.push(math(sta.top()));
                    sta.pop();
                }
                sta.push(str[i]);
            }//運算符為‘+’，‘-’就清棧

            else if(str[i]=='*'||str[i]=='/'){
                if(!sta.empty()&&(sta.top()=='*'||sta.top()=='/')){
                    num.push(math(sta.top()));
                    sta.pop();
                }
                sta.push(str[i]);
            }//運算符為‘*’，‘/’時，先判斷前方是否是‘*’，‘/’，若是就按運算順序算前一個運算符，否者此運算符進棧
        }
        /*********************** for *************************/
        while(!sta.empty()){
                nnum=math(sta.top());
                sta.pop();
                num.push(nnum);
            }//清空剩餘棧
            printf("%.2lf\n",num.top());
            num.pop();
            memset(str,0,sizeof(str));
    }
    return 0;
}
           

轉載請注明出處：http://blog.csdn.net/jinjide_ajin/article/details/47186649