用兩種方式實現(xiàn)表達式自動計算

1、數(shù)據(jù)結(jié)構(gòu)（雙語）項目文檔報告用兩種方式實現(xiàn)表達式自動計算專 業(yè)： 計算機科學與技術(shù) 班 級： 14接計 指導教師： 姓 名： 學 號： 目 錄一、設計思想.03二、算法流程圖.04三、源代碼.06四、運行結(jié)果.13五、遇到的問題及解決.14六、心得體會.15一、設計思想1中綴轉(zhuǎn)換后綴： 定義兩個棧S1，與S2。S1主要管轉(zhuǎn)換專用，S2主要管計算專用。掃描字符串，如果是字符或者小數(shù)的，直接進棧。如果是“（”，同直接進棧，直到遇到“）”，為止。開始處理運算符。如果棧定的運算符的優(yōu)先級低于讀到的那個，那么就直接進棧，否則把棧里的都進數(shù)組里。運算完，直到讀完為止。返回字符數(shù)組，后綴表達式就出來了。然后

2、計算后綴表達。開始依次掃描數(shù)組，如果是數(shù)，就進棧，如果是運算符，那么就把棧的數(shù)彈出一個，賦值給一個變量，再彈一個賦值一個變量，再進行計算，完后再進棧。重復過程，直到度完。棧頂元素就是最終結(jié)果。結(jié)束。2.中綴直接計算：如果獲取的操作符a的優(yōu)先級高于操作符棧棧頂元素b的優(yōu)先級，則a直接入操作符棧;如果獲取的操作符a的優(yōu)先級低于操作符棧棧頂元素b的優(yōu)先級，則b出棧，a進棧，并且取出操作數(shù)棧的棧頂元素m，再取出操作數(shù)棧新的棧頂元素n，如果b為+，則用n+m，若為減號，則n-m，依此類推，并將所得結(jié)果入操作數(shù)棧；如果獲取的是“（”，則直接進操作符棧；如果獲取的是“）”，則操作符棧的棧頂元素出棧,做類似于

3、情況2的計算，之后把計算結(jié)果入操作數(shù)棧，再取操作符棧頂元素，如果不是“（”，則出棧，重復操作，直到操作符棧頂元素為“（”，然后“（”出棧；當表達式中的所有元素都入棧后，看操作符棧中是否還有元素，如果有，則做類似于情況2 的計算，并將結(jié)果存入操作數(shù)棧，則操作數(shù)棧中最終的棧頂元素就是所要求的結(jié)果。二、算法流程圖1.后綴開始用戶輸入表達式將表達式存入到數(shù)組exp構(gòu)造一個操作符棧和一個存放后綴表達式的數(shù)組從exp中獲取元素是否為數(shù)存入后綴數(shù)組中是否為或優(yōu)先級是否高于操作符棧棧頂元素優(yōu)先級進操作數(shù)棧操作符棧里棧頂元素出棧，并存入到后綴數(shù)組中，然后從數(shù)組里取的元素入操作符棧是否為“（”進操作符棧操作符棧里

4、元素出棧，并依次存入到后綴數(shù)組中，直到棧頂元素為“（”，“（”出棧數(shù)組內(nèi)元素是否取盡操作符棧內(nèi)元素全部出棧，并依次存入到后綴數(shù)組中，則得后綴表達式結(jié)束2.中綴直接計算開始從后綴數(shù)組中獲取元素是否為數(shù)存入操作數(shù)棧中為操作符，則從操作數(shù)棧中取值作相應操作后綴數(shù)組中是否還有元素棧里最終棧頂元素即為最終結(jié)果結(jié)束三、源代碼1.后綴表達式#include<stdio.h> #include <string.h> #include<stdlib.h> #include <string> #include <stack> #include<al

5、gorithm> #include "fstream.h"#define MAXN 1000 using namespace std; stack<char> S1; /定義棧S1 ，轉(zhuǎn)換專用stack<double> S2; /定義棧S2，計算專用char *tranfExp(char* exp) /變換后綴 char tempStr1000;/保存后綴表達式的字符串 char ch; int i=0,j=0; int a=0; /標記表達式是否正確專用 /int b=0; /標記數(shù)字格式是否正確待用 while(expi !='0&

6、#39;) if(expi>='0' &&expi<='9')|expi='.') /數(shù)字直接進字符串 tempStrj+ = expi; /tempStrj = ' ' else if(expi = '(' ) /左括號蹦進棧S1 S1.push(expi); else if(expi = ')' ) /如果是右括號，就把左括號后面的運算符都進字符串 while(S1.empty() = false)tempStrj+=S1.top(); /括號里進數(shù)組S1.pop()

7、; /進一個，蹦一個if(S1.top()='(') S1.pop(); /蹦出去(break; else if(expi = '+' | expi = '-') /如果遇到了加后者減號 while(S1.empty() = false)ch=S1.top();if(ch = '+' |ch = '-' |ch = '(') /與棧頂比較優(yōu)先級，同級直接進棧S1.push(expi);break;else /不同級，S1棧里的東西都進字符串里 while(S1.empty() = false) te

8、mpStrj+ = S1.top(); /進一個，蹦一個 S1.pop(); if(S1.top()='(') /如果有括號就把括號前面的進串，括號后的不進 break;if(S1.empty()=true) /如果S1里的東西都進字符串了，變成空了，就把掃描遇到的東西，蹦進S1S1.push(expi); else if(expi = '*' | expi = '/') S1.push(expi); elseprintf("你輸入的不對!");a=1;break; /異常處理 i+; while(S1.empty() = f

9、alse) /最后把S1中的所有運算符彈出棧 if(a=1) break;elsetempStrj+ = S1.top(); /進一個，蹦一個S1.pop(); tempStrj = '0' /最后一個賦值為空 字符串結(jié)束的標志 if(a=1)return 0;else return tempStr; /返回得到的后綴表達式 double calcExp(char* exp) /計算 int i=0; while(expi != '0') if(expi >= '0' && expi <= '9')|e

10、xpi='.') /把數(shù)進棧S2，遇到運算符，就彈2個數(shù)計算，結(jié)果再進S2 if(expi='.') /小數(shù)處理專用 double x=0; double y=0; x=S2.top(); printf("X的值%fn",x); S2.pop(); i+;y=expi-'0' printf("y的值%fn",y); x=x+y/10; printf("X的值%fn",x); S2.push(x); else S2.push(expi-'0'); printf("

11、進棧計算的數(shù)%fn",S2.top(); else if(expi = '-') double m = S2.top(); S2.pop(); double n = S2.top(); S2.pop(); S2.push(n-m); else if(expi = '+' ) double m = S2.top(); / printf("M的值%dn",m); S2.pop(); double n = S2.top(); / printf("N的值%dn",n); S2.pop(); S2.push(n+m); e

12、lse if(expi = '/') double m = S2.top(); S2.pop(); double n = S2.top(); S2.pop(); S2.push(n/m); else if(expi = '*') double m = S2.top(); S2.pop(); double n = S2.top(); S2.pop(); S2.push(n*m); i+; return S2.top(); main() char str1000; char str11000; char* tranStr; int len; double rel;

13、/最后結(jié)果 tranStr = (char *)malloc(100*sizeof(char); printf("輸入字符n"); scanf("%s",str); printf("轉(zhuǎn)換成后綴表達式n");tranStr = tranfExp(str);len=strlen(tranStr); puts(tranStr); for(int i=0;i<=len;i+) /直接傳tranStr會發(fā)生莫名其妙的錯誤，所以重新定義了個數(shù)組，把串全傳送過去str1i=tranStri;rel=calcExp(str1); printf(

14、"結(jié)果為%fn",rel); 2.中綴直接計算#include<iostream> #include<string> #include<stack> using namespace std; int transform(char s,char stored)/轉(zhuǎn)化 const int a8=-1,-1,2,1,0,1,0,2;/保存優(yōu)先級 int i,j,temp; stack<char> sk; for(i=0,j=0,temp=0;si!='0'i+)/j保存數(shù)組stored的有效數(shù)字的長度 if(si&g

15、t;='0'&&si<='9') temp=temp*10+si-'0' else if(temp!=0) storedj+=temp+'0' temp=0; if(!sk.empty()&&sk.top()=')')/彈出) sk.pop(); if(sk.empty()/空就壓入 sk.push(si); else if(asi-'('=ask.top()-'(')/這里看看ASCii表就明白了 storedj+=sk.top(); sk.p

16、op(); sk.push(si); else if(asi-'('<ask.top()-'('&&si!='(')|si=')') while(!sk.empty()&&sk.top()!='(')/停止標志 storedj+=sk.top(); sk.pop(); if(!sk.empty() sk.pop(); sk.push(si); else sk.push(si); storedj+=temp+'0'/最后的數(shù)字也要拿 while(!sk.empty

17、()/殘余運算符 storedj+=sk.top(); sk.pop(); return j; int calcular(char stored,int n) stack<int> cal; int i,x,y,result=0; for(i=0;i<n;i+) if(storedi='+'|storedi='-'|storedi='*'|storedi='/')/遇到運算符 y=cal.top(); cal.pop(); x=cal.top(); cal.pop(); switch(storedi)/各種運算

18、case '+':result=x+y;break; case '-':result=x-y;break; case '*':result=x*y;break; case '/':result=x/y; cal.push(result);/保存當前結(jié)果 else cal.push(storedi-'0'); return result; int main() char s1000; char stored1000; int n,result; while(cin>>s) n=transform(s,stored); result=calcular(stored,n); cout<<result<<endl; return 0; 四、運行結(jié)果1.后綴輸入結(jié)果2.中綴直接計算輸入結(jié)果五、遇到的問題及解決經(jīng)過一個星期的寫代碼，我遇到了很多問題，并一一解決了，比如一些莫名其名的錯誤，都是