一、背景

自己希望通过这个处女帖，来互相学习、经验积累，故将本次课设的代码发到CSDN，希望可以得到网友们的指点。我用的是DEVC++，作出来后，能实现简单的整数加减乘除。

二、代码

1、数据结构

下面展示全部的头文件。

//简单的计算器
#include<iostream>
#include<cstring>
#include<math.h>
#include<windows.h>
#define E 10000000	//定义一个极大值，读取到加减乘除时将加减乘除+E，
//压入int类型栈里，表示加减乘除 
#define MAXSIZE 100 //栈容量 using namespace std;
typedef char ElemType;typedef struct {	//定义char栈 ElemType *base;	//栈底指针 ElemType *top;	//栈顶指针 int stacksize;	//栈的容量 
}SqStack;
typedef struct {	//定义int栈 int *base;int *top;int stacksize;
}SqStack_int;//分别初始化char、int类型栈 
int InitStack(SqStack &S);	//S为要初始化的栈 
int InitStack_int(SqStack_int &S);//S为要初始化的栈 //分别做char、int类型栈的入栈出栈 
int Push_char(SqStack &S,ElemType e);	//S为要初始化的栈 ,e为要入栈元素 
int Push_int(SqStack_int &S,int e);	//S为要初始化的栈 ,e为要入栈元素
char Pop_char(SqStack &S,ElemType &e);//S为要初始化的栈 ,e为要出栈元素
char Pop_int(SqStack_int &S,int &e);//S为要初始化的栈 ,e为要出栈元素
ElemType GetTop(SqStack S);	//返回ElemType类型S栈顶元素 
int Empty(SqStack S);	//S栈判空 
int Length(SqStack_int S);	//返回int类型S栈元素个数 
int replace(char a);	//给运算符a赋值 
int compare(char a,char b);	//a为栈顶运算符，b为扫描到的运算符，返回他们优先级对比的结果 
void count(int a[],int m);	//计算 后缀表达式a的值并输出 ，m表示表达式位数 
int jisuan();	//中缀转后缀，并且划分各个整数 ，返回运算状态，s值控制是否进行该操作 
void xunhuan(int x);//循环函数，让用户循环多次使用 ，x值控制是否循环和判断用户输入正确与否 
void rel(SqStack_int &S,SqStack &S_num,SqStack &S_fuhao,char x);//判断优先级并且入栈出栈

2、弟弟行为的编程

int main(){	//主函数 system("mode con cols=38 lines=25");//窗口宽度高度char s;			//char类型的s做判断用户是否进入计算器的控制元素 printf("欢迎使用简单计算器！\n该计算器可以运算多位的正负整数\n");	//使用指导 system("title 简单计算器");    //设置cmd窗口标题system("color 0c");		// 设置窗口颜色 printf("是否使用计算器（Y/N）："); 	//用户输入Y/N进行选择是否进入计算器 cin>>s;		//用户输入 if(s=='N')	printf("已退出计算器！");	//N表示退出，执行退出 while(s!='N'){		//如果不是N，有两种情况进行判断和循环 if(s=='Y'){			//第一种情况：Y则进入计算器 xunhuan(jisuan()); 	//运用循环函数，进行递归循环，实现循环计算 break;	//当上个循环只有用户选择退出时才会结束循环，之后直接break，结束程序 }elseprintf("输入错误，请重新输入，是否使用计算器（Y/N）：");//第二种情况 ：输入错误（不是Y也不是N），继续让用户选择 cin>>s;	//输入s进行循环 }	 return 0;	//程序正常结束 
}int InitStack(SqStack &S)	//SqStack类型S栈初始化 
{S.base=new ElemType[MAXSIZE];	//分配空间 if(!S.base)	return -1;	//如果分配失败返回-1 S.top=S.base;		//初始化为空栈 S.stacksize=MAXSIZE;	//S的容量设为MAXSIZE return 1;} //同上个S栈的初始化 ,只不过这里是SqStack_int 类型的S栈 int InitStack_int(SqStack_int &S)
{S.base=new int[MAXSIZE];if(!S.base)	return -1;S.top=S.base;S.stacksize=MAXSIZE;return 1;} int Push_char(SqStack &S,ElemType e)	//将元素e入SqStack类型的S栈 
{if(S.top-S.base==S.stacksize)	return -1;	//如果栈满则无法入栈 *S.top++=e;	//将e赋值给top指针所指位置，栈顶指针top加一 return 1;	
}//同上面入栈操作，只是入栈元素类型 和栈类型不同 
int Push_int(SqStack_int &S,int e)
{if(S.top-S.base==S.stacksize)	return -1;*S.top++=e;return 1;	
}char Pop_char(SqStack &S,ElemType &e)	//S栈栈顶元素出栈  
{if(S.top==S.base)	return printf("错误");	//如果栈空，返回错误 e=*--S.top;	//栈顶指针减一，之后栈顶元素值赋值给 e return e; 	//返回e值 
}//同上面操作，只是类型不同 
char Pop_int(SqStack_int &S,int &e)
{if(S.top==S.base)	return printf("错误");e=*--S.top;return e; 
}ElemType GetTop(SqStack S)//取S栈栈顶元素 
{if(S.top!=S.base)	//如果S栈非空返回 栈顶元素值 return *(S.top-1);else return '#';	//否则返回"#" 
}int Empty(SqStack S){//判断S栈是否为空 if(S.top-S.base==0)	//栈空返回1，否则返回0 return  1;return 0;
}int Length(SqStack_int S)//求S栈的元素个数 
{return (S.top-S.base);
}int replace(char a)//判断a符号优先级
{switch (a)//考虑运算符a的类型，并且对相应的类型赋值 {case '+':return 1;case '-':return 1;case '*':return 2;case '/':return 2;case '(':return 0;case '#':return 0;}
}
int compare(char a,char b)//对比a和b符号的优先级 
{return (replace(a)<replace(b)) ? 1:0;//如果b优先级大于a则返回0，否则返回1 }
void count(int a[],int m)
//计算元素个数m的表达式a 
{SqStack_int Sw;//定义一个SqStack_int类型的栈Sw InitStack_int(Sw);//Sw栈初始化 for(int h=0;h<m;h++){//循环遍历表达式，判断其中数字是代表运算符还是数字 //10000045、10000042、10000047、10000043分别对应4个运算符 if(a[h]!=10000045&&a[h]!=10000042&&a[h]!=10000047&&a[h]!=10000043){Push_int(Sw,a[h]);//数字入栈 }else{//如果出现上述4个数字，表示是运算符 int c,d,sum;//分类讨论+—*/四种情况，并且求值，最后入栈 if(a[h]==10000045){Pop_int(Sw,c);Pop_int(Sw,d);sum=d-c;Push_int(Sw,sum);}if(a[h]==10000043){Pop_int(Sw,c);Pop_int(Sw,d);sum=c+d;Push_int(Sw,sum);}if(a[h]==10000042){Pop_int(Sw,c);Pop_int(Sw,d);sum=c*d;Push_int(Sw,sum);}if(a[h]==10000047){Pop_int(Sw,c);Pop_int(Sw,d);sum=d/c;Push_int(Sw,sum);}}}int x;Pop_int(Sw,x);//将最后的栈内计算出的最后结果出栈，赋值给x printf("%d\n",x);//输出最后结果x 
}int jisuan()//进行中缀转后缀 
{printf("请输入您想计算的表达式(输入#退出)：\n");//定义SqStack_int类型的栈S，用于存储int类型的最终表达式 SqStack_int S;	//定义SqStack类型的S_num、S_fuhao,用于中缀转后缀用 SqStack S_num,S_fuhao;InitStack_int(S);InitStack(S_num);InitStack(S_fuhao);int tag=0;	//tag的值表示输入的数字以后应该转化为几位数 char e;//e用来存储后面的出栈元素 char ex[100];//定义一个容量为100的字符串，供用户输入表达式 cin>>ex;	//输入 if(ex[0]=='#')	return 1;//如果输入#号表示用户不想继续使用计算器了，则返回1 for(int x=0;ex[x]!='\0';x++){	//判断输入的内容合不合规 if(ex[x]!='+'&&ex[x]!='-'&&ex[x]!='*'&&ex[x]!='/'&&ex[x]!='('&&ex[x]!=')'&&ex[x]!='1'&&ex[x]!='2'&&ex[x]!='3'&&ex[x]!='4'&&ex[x]!='5'&&ex[x]!='6'&&ex[x]!='7'&&ex[x]!='8'&&ex[x]!='9'&&ex[x]!='0'){printf("错误");return -1;	//如果输入的不合规返回-1 }
}for(int i=0;ex[i]!='\0';i++){		//开始遍历字符串 if(ex[i]!='+'&&ex[i]!='-'&&ex[i]!='*'&&ex[i]!='/'&&ex[i]!='('&&ex[i]!=')'){	//遍历到元素是数字 if(i==0&&ex[i]=='0'){	//考虑第一个数字是 0的情况 int a=ex[i]-48;	//将字符类型的0转化成int类型的0 Push_int(S,a);	//入S栈 continue;	//跳过该i值 ，进行下个i值循环 }tag++;			//tag记录数字个数，后面Pop划成一个整数用 Push_char(S_num,ex[i]);//将ex[i] 的值入S_num栈 }else{			//遍历到运算符 if(i==0&&ex[i]=='-'){	//讨论如果第一个数是负数情况 int cn=0,mk=0;for(int j=1;ex[i+j]!='+'&&ex[i+j]!='-'&&ex[i+j]!='*'&&ex[i+j]!='/';j++){	//第一个负数格式为 -xx 是一个整数 cn++;	//判断第一个元素是负数，除第一个负号外，数字所占的位数 }	 for(int k=0;k<cn;k++){// 把入的数字元素划成整数 mk+=(ex[k+1]-48)*pow(10,cn-k-1);//每位累加，最后 mk为最终整数值 }Push_int(S,0-mk);	//压入int栈一个负数，0-mk //跳过这个负数继续向后遍历 i+=cn;	continue;}if(ex[i]=='('&&ex[i+1]=='-'){	//讨论如果是括号内负数情况 int cn=0,mk=0;Push_char(S_fuhao,ex[i]);for(int j=2;ex[i+j]!=')'&&ex[i+j]!='+'&&ex[i+j]!='-'&&ex[i+j]!='*'&&ex[i+j]!='/';j++){	//负数格式必须为（-xx） xx是一个整数 cn++;}	 for(int k=0;k<cn;k++){// 把入的数字元素划成整数 mk+=(ex[i+cn+1-k]-48)*pow(10,k);}Push_int(S,0-mk);	//压入int栈一个负数，0-mk i+=cn+1;	//跳过这个负数继续向后遍历 continue;//进行下一个i值循环 }if(tag==0){			//如果扫描到符号前，tag==0，表示之前没有数字字符 if(Empty(S_fuhao)||ex[i]=='(')	//如果是空栈或者左括号 {Push_char(S_fuhao,ex[i]);//直接入S_fuhao栈 continue;//进行下一个i值循环 }rel(S,S_num,S_fuhao,ex[i]); }//如果扫描到运算符之前tag！=0，则需先Pop出数字字符，进行整合成一个整数 else{int a=0;//a是最后的数字元素整合结果 for(int lk=0;lk<tag;lk++){char ad;Pop_char(S_num,ad);int ax=ad;a+=(ax-48)*pow(10,lk);}Push_int(S,a);//将a入S栈 tag=0;//最后将计数器tag置零 rel(S,S_num,S_fuhao,ex[i]);}}}if(tag!=0){	//处理字符串最后的数字，进行出栈求值再入栈 int a=0;for(int lk=0;lk<tag;lk++){char ad;Pop_char(S_num,ad);int ax=ad;a+=(ax-48)*pow(10,lk);}Push_int(S,a);tag=0;}while(!Empty(S_fuhao)){	//清空符号栈，将剩余的符号出S_fuhao栈，再+E入S栈 Pop_char(S_fuhao,e);Push_int(S,e+E);}int m=Length(S);//m表示栈S的元素个数 int a[m];//a[m] for(int qw=m-1;qw>-1;qw--){Pop_int(S,a[qw]);} count(a,m);//计算后缀表达式 return 2;//如果程序循行到这里，说明是正常运行，返回2 
}void rel(SqStack_int &S,SqStack &S_num,SqStack &S_fuhao,char x)//判断优先级并且 入栈出栈 
{char e;if(x==')'){//如果是右括号 while(GetTop(S_fuhao)!='('){//取S_fuhao 栈的栈顶元素 ，如果不是左括号 //将其中的符号挨个出栈，并且转为int类型元素，再加E Pop_char(S_fuhao,e);Push_int(S,e+E);}	Pop_char(S_fuhao,e);//最后将左括号出栈 }else{//运算符优先级然后入栈 if(compare(GetTop(S_fuhao),x))	 Push_char(S_fuhao,x);//扫描到的元素比栈顶元素优先级高，直接入S_fuhao栈 else{//否则进行S_fuhao栈栈顶元素先出栈后+E入S栈Pop_char(S_fuhao,e);Push_int(S,e+E);while(!compare(GetTop(S_fuhao),x)){//只要扫描到的该符号的 优先级不大于栈顶元素优先级 ，就重复之前的出栈，+E入S栈的操作 Pop_char(S_fuhao,e);Push_int(S,e+E); }Push_char(S_fuhao,x);//最后将这个扫描的运算符入S_fuhao栈 }	}
}void xunhuan(int x){ //循环函数 ，根据x的值进行循环、退出、判断输入是否正确 if(x==-1){	//如果x是-1，则提示输入错误 printf("输入错误，是否重新输入（Y/N）：");char s;//定义一个char类型的s cin>>s;//用户输入s switch(s){//s代表用户在输入错误的表达式时是否还想继续输入表达式求值 case 'Y'://如果s是符号Y xunhuan(jisuan());//继续进行循环计算 case 'N':	//如果s是符号N printf("正在退出...");//表示用户想退出，页面提示正在退出。。。 break;//终止该循环 default://否则表示用户输入的错误 xunhuan(-1); //将-1赋值给该循环函数，继续 让用户进行使用选择 }}if(x==2) xunhuan(jisuan()); //如果x是2，将jisuan()函数带入循环函数，继续运行循环函数，实现循环计算的功能 int i=1;while(i>0){//做一次循环 i--;if(x==1){//如果x是1 ，表明用户想要退出 printf("正在退出...");//提示正在退出。。。 break;//终止该循环 }} 
}

三、基本逻辑

中缀转后缀

（1）为什么要转

因为我们平时计算的表达式都是中缀表达式，但是相比中缀，电脑更喜欢计算后缀表达式。实现逆波兰式的算法，难度并不大，但为什么要将看似简单的中缀表达式转换为复杂的逆波兰式？原因就在于这个简单是相对人类的思维结构来说的。但是对计算机而言中序表达式是非常复杂的结构。相对的，逆波兰式在计算机看来却是比较简单易懂的结构。因为计算机普遍采用的内存结构是栈式结构，它执行先进后出的顺序。

（2）怎么转

说到中缀转后缀表达式，肯定第一想法就是建两个栈，一个存储运算符，一个存储操作数。然后循环遍历扫描输入的字符串，遇到数字直接入操作数栈，遇到运算符分类讨论，最后将整个字符串都入到操作数栈。最后转成后缀表达式。

但是我所做的还与这个有些不同，因为传统的中缀转后缀一般都是1位数的，如果要实现多位数，还需要对字符串类型数字进行划分整合。所以多位数相比个位数的中缀转后缀可以说是有些难了。

具体思想如下：

我是定义并初始化了三个栈；S，S_num,S_fuhao,S用于存储最终的后缀表达式，S_num作为中转站，存储字符串类型的数字，通过入栈出栈，进行操作数整合，并且类型装换成int，入S栈，而S_fuhao也是一个中转栈，将转成后缀的符号入S栈。
依旧先是循环遍历，因为输入的是字符串，所以并不是一个数字代表一个int型整数，得用一个tag计数器进行位数记录，然后扫描到运算符后，根据tag值进行字符串型的数字划分，将各个字符串型的数字整合成各自的int型整数。遇到左括号和右括号依旧跟传统处理办法一样，遇到左括号直接入栈，遇到右括号扫描之前的符号，直到扫描到左括号，将括号内的符号和操作数进行出入栈操作，最后将左括号出栈。遇到加减乘除，则开始判断优先级。之后进行出栈入栈操作，在最终入栈时，我直接定义了一个E，E的值为1亿，将加减乘除最终入S栈时都与E相加，将这4个破亿的int型整数代表加减乘除，这样S栈内的数据只要不是破亿，都不会影响结果。以此循环，最后清理S_num和S_fuhao栈，将里面的剩余元素出栈，入S栈。

（3）注意事项

1.因为输入的是字符串，所以并不是一个数字代表一个int型整数，得用一个tag计数器进行位数记录，然后扫描到运算符后，根据tag值进行字符串型的数字划分，将各个字符串型的数字整合成各自的int型整数。
2.考虑负数所在的位置（首位：“-3+2”，中间：“3*（-3）”）
3.考虑字符0在开头想要表示的数字就是int型的0该如何处理
4.运算符优先级判断

下面展示一下运算符优先级比较代码

int replace(char a)//判断a符号优先级
{switch (a)//考虑运算符a的类型，并且对相应的类型赋值 {case '+':return 1;case '-':return 1;case '*':return 2;case '/':return 2;case '(':return 0;case '#':return 0;}
}
int compare(char a,char b)//对比a和b符号的优先级 
{return (replace(a)<replace(b)) ? 1:0;//如果b优先级大于a则返回0，否则返回1 }