題目描述

在數據結構課上，老師給大家布置了一個表達式計算的問題 3*2+1*5. It's so easy!!! csw同學做了很不過癮，他想求解更復雜的表達式: 比如(123+456)/789. 但一時之間他想不出好的辦法，諸位就幫幫他吧.

輸入

輸入包括多組數據, 每組測試數據占一行, 包含一個字符串(長度不超過100), 表示要運算的表達式.

輸出

對應每組測試數據, 輸出計算結果(保留三位有效數字) --- 計科1702項方頌更正“保留三位小數，不是三位有效數字”

樣例輸入

(123+456)/789

樣例輸出

0.734

思路：

先將題目給定的中綴表達式轉為后綴表達式，再對后綴表達式進行處理計算，注意題目中有多組輸入

中綴表達式轉后綴表達式規則：

1.遇到數字就直接輸入進后綴表達式中，遇到操作符則先判斷優先級，再輸入到棧中

2.如果棧頂元素優先級大于等于當前操作符，則先將棧頂元素彈出并輸入到后綴表達式中，再將當前操作符壓入棧中

3.如果遇到左括號，則直接將其壓入棧中，如果遇到右括號，則彈出棧中元素，直到遇到左括號為止，并將這些元素輸出到后綴表達式中（也要進行優先級判斷）

4.最后，將棧中剩余元素壓入棧中

后綴表達式計算規則：

1.讀取到數字就直接入棧
2.當讀入運算符就直接將棧中前兩個數彈出，其中先彈出的為右操作數，后彈出的為左操作數，計算之后將結果壓入棧中。
3.直至讀取完畢，棧中剩余的數據的就是結果

其實我感覺我的代碼是有一些問題的，但是oj能過，所以不管了(*^▽^*)

#include<stdio.h>
#include<string.h>
int main()//先轉為后綴表達式，再進行計算
{char ss[200];while(scanf("%s",ss)!=EOF){//多組輸入if(ss[0]=='\n')break;//退出條件char a,st[1001],s[1001];//st為棧，s為后綴表達式memset(st,'\0',sizeof(st));int top=-1,k=0;int flag=0;//用于判斷該數字是否結束，若結束則要在后綴表達式里注入一個空格for(int i=0;i<strlen(ss);i++){a=ss[i];if(flag==1&&(s[k-1]>='0'&&s[k-1]<='9'))//當前數字結束，并且后面一個字符仍然是數字
//此時需要輸入一個空格用于隔開兩個數字{s[k++]=' ';flag=0;}if(a>='0'&&a<='9')//遇到數字直接放入后綴表達式中{s[k++]=a;}else if(a=='+'||a=='-'){if(s[k-1]>='0'&&s[k-1]<='9')//這一步判斷是否需要加空格flag=1;while(st[top]=='+'||st[top]=='-'||st[top]=='*'||st[top]=='/'){//棧頂元素優先級大于等于當前操作符，彈出并輸入到后綴表達式里s[k++]=st[top];top--;flag=0;}st[++top]=a;//當前操作符入棧}else if(a=='*'||a=='/')//和上一塊else if同理{if(s[k-1]>='0'&&s[k-1]<='9')flag=1;while(st[top]=='*'||st[top]=='/'){s[k++]=st[top--];flag=0;}st[++top]=a;}else{if(a=='(')//遇到左括號，左括號入棧{st[++top]=a;}else{//遇到右括號char temp[100];//用于存儲彈出的操作符int t=0;while(st[top]!='(')//彈出棧中，直到遇到左括號（棧頂元素為左括號）{temp[t++]=st[top--];}top--;//把左括號出棧for(int i=t-1;i>=0;i--)//優先級高的先入棧{if(temp[i]=='*'||temp[i]=='/')s[k++]=temp[i];}for(int i=t-1;i>=0;i--)//優先級低的后入棧{if(temp[i]=='+'||temp[i]=='-')s[k++]=temp[i];}flag=0;}}}while(top!=-1)//剩余元素入棧{s[k++]=st[top--];}//轉化完成double stt[100];//新棧int ttop=-1;memset(stt,0,sizeof(stt));int temp1=0;double tempp=0;for(int i=0;i<k;i++){if(s[i]<='9'&&s[i]>='0')//讀取數字{temp1=temp1*10+(s[i]-'0');}else if(s[i]==' ')//當前數字結束，壓入棧中{stt[++ttop]=temp1;temp1=0;}else if(s[i]=='+')//將棧中最上面兩個元素相加，并放入棧頂{if(s[i-1]>='0'&&s[i-1]<='9'){//如果當前數字還沒入棧，則先將當前正在讀取的數字入棧stt[++ttop]=temp1;temp1=0;}tempp=stt[ttop]+stt[ttop-1];ttop-=1;stt[ttop]=tempp;}else if(s[i]=='-')//后面三個同理{if(s[i-1]>='0'&&s[i-1]<='9'){stt[++ttop]=temp1;temp1=0;}tempp=stt[ttop-1]-stt[ttop];ttop--;stt[ttop]=tempp;}else if(s[i]=='*'){if(s[i-1]>='0'&&s[i-1]<='9'){stt[++ttop]=temp1;temp1=0;}tempp=stt[ttop-1]*stt[ttop];ttop--;stt[ttop]=tempp;}else if(s[i]=='/'){if(s[i-1]>='0'&&s[i-1]<='9'){stt[++ttop]=temp1;temp1=0;}tempp=stt[ttop-1]/stt[ttop];ttop--;stt[ttop]=tempp;}}printf("%.3lf\n",stt[ttop]);//題目要求保留三位小數，輸出memset(ss,0,sizeof(ss));//初始化一下}
}