Question

如何用栈编写计算器？

Answer 1

一、需求分析
1、 功能：疏如一行表达式，若表达式有误，则输出“表达式有错” ，否则计算出表达式的值并输出。 运算符包括加、减、乘、除、乘方、一目减。 括号均为小括号，但可以层层嵌套。操作数可以是浮点数，也包括有多个字母组成的变量。
2、 输入的形式为表达式，按回车结束。输入值的范围不超过浮点数的范围。含有变量，变量名由字母组成，大小写不限。
3、 若计算结果为整数，则输出整数，若含有小数，则输出浮点数。
二、概要设计
1、 总体思路，先读入一行表达式，用一个字符数组存储。然后依次读每个字符，进行判断。边读入边进行计算。程序中用到了两个栈，一个字符栈以及一个数字栈，分别用来存储运算符和数字，根据运算符的优先顺序进行计算。最后输出结果。

2、程序包括几个模块，主函数和几个基本函数。
说明几个函数：
bool stackempty(save1 s)用来判断操作数栈s是否为空。
void push(save1 &s,char e)若栈满则输出“栈已满”，否则将元素e入栈
void pop(save1 &s, char &e)若栈为空则输出“栈为空”，否则将栈顶元素赋给e
bool stackempty2(save2 s)用来判断运算符栈s是否为空。
void push2(save2 &s, char e)若运算符栈满则输出“栈已满”，否则将元素e入栈
void pop2(save2 &s, char &e)若栈为空则输出“栈为空”，否则将栈顶元素赋给e
int in(char e)返回运算符e在栈内的优先级别
int out(char e) 返回运算符e在栈外的优先级别
void count(char a,char ope, char b)将a、b进行相应的运算，并将运算结果入栈
3、具体操作步骤：
1、先读入一行表达式，用一个字符数组line[]存储
2、依次读入每个字符并进行处理同是进行表达式判错：
1. 遇数字，则继续判断下一个字符，直到下一个字符不是数字且不是小数点，若该数含有两个小以上数点，则表示输入错误。否则即可保证该操作数是完整的浮点数，然后将该数入操作数栈。

若数字不是表达式的最后一位，且数字后面跟的不是“+、-、*、/、^、)”，则为表达式错误

2. 遇运算符，则分两种情况：
1、若运算符为负号（该运算符为符号的情况有两种：一为负号在最开头，一为符号前面是“（” ），则先将0入操作数栈，然后再将负号入运算符栈。
2、该运算符不是负号则与运算符栈的栈顶元素比：
(1) 若栈顶元素优先级低， 新输入的运算符入栈。
(2) 若栈顶元素优先级高，
1) 从符号栈弹出一个运算符，
2) 从对象栈弹出一个/两个操作数，
3) 运算结果压入对象栈。
(3) 优先级相等，则栈顶元素出栈，与输入元素对消。

若“(、+、-、*、/、^”放在表达式最后面，则表达式错误
若“+、-、*、/、^”后面跟的不是数字或者变量，表达式错误

3、遇字母变量，则继续判断下一个字符，直到下一个字符不是字母变量，即可保证该变量是完整的，然后输出“请输入变量的值”，再将输入的变量值入操作数栈。
若变量后面跟的不是“+、-、*、/、^、)”，则表达式错误
4、若所读的该字符不是上述情况中的一种，则表达式错误

3、当将所有的字符都读一遍之后，若表达式正确的话，则必然不含有“（”或者“）”。即若运算符栈中含有“（”或者“）”，则表达式必错误。 再考虑表达式正确的情况：运算符栈可能为空，则操作符栈中必剩下一个操作数，即最后的结果。若不为空，则留在运算符栈中的运算符的优先级别从栈顶至栈底依次递减。故可从运算符栈顶开始弹出一个运算符，从操作数栈中弹出两个操作数进行运算，再将运算结果入操作数栈，一直循环至运算符栈为空。此时操作数栈剩下的唯一一个操作数就是运算结果。

三、结论及体会
1、实验结论
a)、实验完成了题目的要求，自己添加了对浮点数的操作，并进行判错。
b)、编写代码基本上能够满足编程规范的要求，代码的变量命名，以及注释的书写，基本能按照要求进行。
b)、将数据结构中的队列和堆栈的知识复习到，并且学会创新，在代码的编写中，学习了编程规范，学习了结构化编程。

2、实验体会
a)、通过本设计实验将数据结构中的堆栈和队列的知识复习到，并且能够自己设计一些东西，学会了在设计实验过程时的基本步骤。基本上能够有条理的解决这些问题。
b)、在试验中遇到了很多的问题，都是以前没有发现的，这些问题设计的方面很多，有以前的C++基础的，也有最近学习的数据结构的知识。通过实验的设计，让我发现了自己的不足。自己在学习知识上面的漏洞。自己在细节方面的考虑还不够全面，很多细节都是通过调试才发现的。比如刚开始时忘了考虑变量之前有负号的情况以及将整个式子读一遍之后，栈中的操作数可能还有剩，还得继续进行计算等。希望通过弥补这些发现的漏洞，提高自己的专业知识水平。
c)、设计过程中的解决问题的方法，让我明白了如何学习会更有效。如何学习才不会耽误太多的时间。也学会了解决问题的一般方法：向老师、同学请教，借助网络等等。
d)、实验过程中也走了很多的弯路，由于在开始设计的时候思路不时很清晰，对于一些问题不能很好的提出解决问题的方法，在设计过程中，代码总是重复的修改，在很多问题上，代码并不时最优的。相信在以后的学习中，随着知识的增多，问题会逐渐得到解决。
四、程序源代码
#include<iostream>
#include<cmath>
#include<cstdlib>
using namespace std;
#define MAX 1000

struct save1
{
float n[MAX];
int top;
}stack1;

struct save2
{
char n[MAX];
int top;
}stack2;
//stack1存储数字，stack2存储运算符号.

bool stackempty(save1 s)//判断是否为空
{
if (s.top== -1)
return 1;
else
return 0;
}

bool stackempty2(save2 s)//判断是否为空
{
if (s.top== -1)
return 1;
else
return 0;
}

void push(save1 &s,float e)//将e入栈
{
if(s.top==MAX-1)
{
cout<<"栈已满"<<endl;
return ;
}
s.top++;
s.n[s.top]=e;
}

void push2(save2 &s,char e)//将e入栈
{
if(s.top==MAX-1)
{
cout<<"栈已满"<<endl;
return ;
}
s.top++;
s.n[s.top]=e;
}

void pop(save1 &s,float &e)//将栈顶元素出栈，存到e中
{
if(s.top==-1)
{ cout<<"栈为空"<<endl; }
else
{e=s.n[s.top]; s.top--; }
}

void pop2(save2 &s,char &e)//将栈顶元素出栈，存到e中
{
if(s.top==-1)
{ cout<<"栈为空"<<endl; }
else
{e=s.n[s.top]; s.top--; }
}

int in(char e)//e在栈内的优先级别
{
if(e=='-' || e=='+') return 2;
if(e=='*' || e=='/') return 4;
if(e=='^') return 5;
if(e=='(') return 0;
if(e==')') return 7;
return -1;
}

int out(char e)//e在栈外的优先级别
{
if(e=='-' || e=='+') return 1;
if(e=='*' || e=='/') return 3;
if(e=='^') return 6;
if(e=='(') return 7;
if(e==')') return 0;
return -1;
}

void count(float a,char ope,float b)//进行计算并将计算结果入栈
{
float sum;
if(ope=='+') sum=a+b;
if(ope=='-') sum=a-b;
if(ope=='*') sum=a*b;
if(ope=='/') sum=a/b;
if(ope=='^') sum=pow(a,b);
push(stack1,sum);
}

int main()
{
int i=0,len,j,nofpoint,g=0;//len表示输入式子的长度。 g表示读入的字符是否是字母变量、数字以及运算符。
float a,b;//a、b用来存储操作数栈中弹出的操作数，便于代入函数中进行计算。
char line[MAX],operate,temp[20];
cout<<"请输入表达式"<<endl;
cin>>line;
len=strlen(line);
stack1.top=-1;//将栈置为空
stack2.top=-1;//将栈置为空
while(1)
{
g=0;
if(isdigit(line[i]))//若读入的字符为数字，则继续判断下一个字符，直到下一个字符不是数字或者不是小数点，即可保证该操作数是完整的小数，然后将该数入操作数栈。
{
j=0; g=1;
nofpoint=0;//记录所存的数中小数点的个数
while(isdigit(line[i]) || line[i]=='.')
{
if(line[i]=='.') nofpoint++;
temp[j++]=line[i];
i++;
if(i>=len) break;
}
if( nofpoint>1 || (i<len&&(line[i]!='-' && line[i]!='+' && line[i]!='*' && line[i]!='/' && line[i]!='^' && line[i]!=')')) )
{ cout<<"表达式有错"<<endl; return 0; }//所存数中含有不止一个小数点，或者数字后面跟的不是“+、-、*、/、^、)”，则为错误

temp[j]='\0';
b=atof(temp);
push(stack1,b);
if(i>=len) break;
}
else
{
if(line[i]=='-' || line[i]=='+' || line[i]=='*' || line[i]=='/' ||
line[i]=='^' || line[i]=='(' || line[i]==')' ) //若读入的字符为运算符的情况
{
g=1;
if(line[i]=='(' && i==len) { cout<<"表达式有错"<<endl; return 0; }// “(”放表达式最后面，错误
if(line[i]=='-' || line[i]=='+' || line[i]=='*' || line[i]=='/' || line[i]=='^')
{
if(i==len) { cout<<"表达式有错"<<endl; return 0; }//“+、-、*、/、^”放在表达式最后面，错误
if( (!isdigit(line[i+1])) && (!isalpha(line[i+1])) && line[i+1]!='(')//“+、-、*、/、^”后面跟的不是数字或者变量，错误
{ cout<<"表达式有错"<<endl; return 0; }
}

if(line[i]=='-' && (i==0 || line[i-1]=='(' ))//运算符是负号
{
push(stack1,0);
push2(stack2,line[i]);
i++;
}
else
{ //读入的运算符与运算符栈的栈顶元素相比，并进行相应的操作
if(in(stack2.n[stack2.top])<out(line[i])||stackempty2(stack2)) { push2(stack2,line[i]);i++;}
else
if(in(stack2.n[stack2.top])==out(line[i])) {i++; stack2.top--;}
else
if(in(stack2.n[stack2.top])>out(line[i]))
{
pop(stack1,a);
pop(stack1,b);
pop2(stack2,operate);
count(b,operate,a);
}
if(i>=len) break;
}
}
else
{
if(isalpha(line[i]))//读入的字符是字母变量的情况
{
g=1;
cout<<"请输入变量";
while( isalpha(line[i])) { cout<<line[i]; i++; }
cout<<"的值"<<endl;
cin>>b;
push(stack1,b);
if(i>=len) break;
if(line[i]!='-' && line[i]!='+' && line[i]!='*' && line[i]!='/' && line[i]!='^' && line[i]!=')')//变量后面跟的不是“+、-、*、/、^、)”，则为错误
{ cout<<"表达式有错"<<endl; return 0; }
}
}
}
if(g==0) { cout<<"表达式有错"<<endl; return 0; }//g=0表示该字符是不符合要求的字符
}

while(stack2.top!=-1)//读入结束后，继续进行操作，直到运算符栈为空
{
pop(stack1,a);
pop(stack1,b);
pop2(stack2,operate);
if(operate=='(' || operate==')') //括号多余的情况
{ cout<<"表达式有错"<<endl; return 0; }
count(b,operate,a);
}
cout<<stack1.n[stack1.top]<<endl;
return 0;
}