用两种方式实现表达式自动计算

1、数据结构（双语）项目文档报告用两种方式实现表达式自动计算专 业： 计算机科学与技术 班 级： 14接计 指导教师： 姓 名： 学 号： 目 录一、设计思想.03二、算法流程图.04三、源代码.06四、运行结果.13五、遇到的问题及解决.14六、心得体会.15一、设计思想1中缀转换后缀： 定义两个栈S1，与S2。S1主要管转换专用，S2主要管计算专用。扫描字符串，如果是字符或者小数的，直接进栈。如果是“（”，同直接进栈，直到遇到“）”，为止。开始处理运算符。如果栈定的运算符的优先级低于读到的那个，那么就直接进栈，否则把栈里的都进数组里。运算完，直到读完为止。返回字符数组，后缀表达式就出来了。然后

2、计算后缀表达。开始依次扫描数组，如果是数，就进栈，如果是运算符，那么就把栈的数弹出一个，赋值给一个变量，再弹一个赋值一个变量，再进行计算，完后再进栈。重复过程，直到度完。栈顶元素就是最终结果。结束。2.中缀直接计算：如果获取的操作符a的优先级高于操作符栈栈顶元素b的优先级，则a直接入操作符栈;如果获取的操作符a的优先级低于操作符栈栈顶元素b的优先级，则b出栈，a进栈，并且取出操作数栈的栈顶元素m，再取出操作数栈新的栈顶元素n，如果b为+，则用n+m，若为减号，则n-m，依此类推，并将所得结果入操作数栈；如果获取的是“（”，则直接进操作符栈；如果获取的是“）”，则操作符栈的栈顶元素出栈,做类似于

3、情况2的计算，之后把计算结果入操作数栈，再取操作符栈顶元素，如果不是“（”，则出栈，重复操作，直到操作符栈顶元素为“（”，然后“（”出栈；当表达式中的所有元素都入栈后，看操作符栈中是否还有元素，如果有，则做类似于情况2 的计算，并将结果存入操作数栈，则操作数栈中最终的栈顶元素就是所要求的结果。二、算法流程图1.后缀开始用户输入表达式将表达式存入到数组exp构造一个操作符栈和一个存放后缀表达式的数组从exp中获取元素是否为数存入后缀数组中是否为或优先级是否高于操作符栈栈顶元素优先级进操作数栈操作符栈里栈顶元素出栈，并存入到后缀数组中，然后从数组里取的元素入操作符栈是否为“（”进操作符栈操作符栈里

4、元素出栈，并依次存入到后缀数组中，直到栈顶元素为“（”，“（”出栈数组内元素是否取尽操作符栈内元素全部出栈，并依次存入到后缀数组中，则得后缀表达式结束2.中缀直接计算开始从后缀数组中获取元素是否为数存入操作数栈中为操作符，则从操作数栈中取值作相应操作后缀数组中是否还有元素栈里最终栈顶元素即为最终结果结束三、源代码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 ，转换专用stack<double> S2; /定义栈S2，计算专用char *tranfExp(char* exp) /变换后缀 char tempStr1000;/保存后缀表达式的字符串 char ch; int i=0,j=0; int a=0; /标记表达式是否正确专用 /int b=0; /标记数字格式是否正确待用 while(expi !='0&

6、#39;) if(expi>='0' &&expi<='9')|expi='.') /数字直接进字符串 tempStrj+ = expi; /tempStrj = ' ' else if(expi = '(' ) /左括号蹦进栈S1 S1.push(expi); else if(expi = ')' ) /如果是右括号，就把左括号后面的运算符都进字符串 while(S1.empty() = false)tempStrj+=S1.top(); /括号里进数组S1.pop()

7、; /进一个，蹦一个if(S1.top()='(') S1.pop(); /蹦出去(break; else if(expi = '+' | expi = '-') /如果遇到了加后者减号 while(S1.empty() = false)ch=S1.top();if(ch = '+' |ch = '-' |ch = '(') /与栈顶比较优先级，同级直接进栈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' /最后一个赋值为空 字符串结束的标志 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='.') /把数进栈S2，遇到运算符，就弹2个数计算，结果再进S2 if(expi='.') /小数处理专用 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、进栈计算的数%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、/最后结果 tranStr = (char *)malloc(100*sizeof(char); printf("输入字符n"); scanf("%s",str); printf("转换成后缀表达式n");tranStr = tranfExp(str);len=strlen(tranStr); puts(tranStr); for(int i=0;i<=len;i+) /直接传tranStr会发生莫名其妙的错误，所以重新定义了个数组，把串全传送过去str1i=tranStri;rel=calcExp(str1); printf(

14、"结果为%fn",rel); 2.中缀直接计算#include<iostream> #include<string> #include<stack> using namespace std; int transform(char s,char stored)/转化 const int a8=-1,-1,2,1,0,1,0,2;/保存优先级 int i,j,temp; stack<char> sk; for(i=0,j=0,temp=0;si!='0'i+)/j保存数组stored的有效数字的长度 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'/最后的数字也要拿 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);/保存当前结果 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; 四、运行结果1.后缀输入结果2.中缀直接计算输入结果五、遇到的问题及解决经过一个星期的写代码，我遇到了很多问题，并一一解决了，比如一些莫名其名的错误，都是