用C++语言实现大整数型计算器
发布网友
发布时间:2022-06-04 15:51
我来回答
共1个回答
热心网友
时间:2023-10-29 13:30
#include "stdafx.h"
#include "iostream.h"
#include "math.h"
#include "time.h"
#define TRUE 1
#define FALSE 0
#define ERROR -1
typedef int Status;
//用模板实现的链式结构堆栈类
template <class T>
class stack{
private:
struct link{
T data; //结点数据域
link *next; //下一结点指针
link(T Data,link* Next){//结构体构造函数
data=Data;
next=Next;
}
}*head; //堆栈顶指针
public:
stack(); //构造函数(初始化栈)
~stack(); //析构函数(销毁栈)
void push(T Data); //压栈操作
T gettop()const; //取栈顶元素
T pop(); //出栈操作
T getvalue(int index); //返回栈底开始第INDEX个栈中值
void traverse(int n); //遍历栈 N个数换行
int empty(); //判断栈是否为空,1是,0非
int sizeofstack(); //返回栈的大小
void clear(); //清空栈
};
//类模板成员函数的实现
template<class T> stack<T>::stack()//构造函数
{
head=0;
}
template<class T> stack<T>::~stack()//析构函数
{
link* cursor=head;
while(head)
{
cursor=cursor->next;
delete head;
head=cursor;
}
}
template<class T>void stack<T>::push(T Data)//压栈操作
{
head=new link(Data,head);
}
template<class T>T stack<T>::gettop()const//取栈顶元素
{
return head->data;
}
template<class T>T stack<T>::pop()//出栈操作
{
if(head==0)return 0;
T result=head->data;
link* oldhead=head;
head=head->next;
delete oldhead;
return result;
}
template <class T>T stack<T>::getvalue(int index)//返回栈底开始第INDEX个栈中值
{
link *cursor=head;
int i=1;
int stacklen=sizeofstack();
if(index<=0||index>stacklen)return 0;
while(i<=(stacklen-index))
{
cursor=cursor->next;
i++;
}
return cursor->data;
}
template <class T> void stack<T>::traverse(int n)//遍历栈
{
link * cursor=head;
int iEnterSign=1;//换行标识
while(cursor)
{
cout<<cursor->data<<" ";
if(iEnterSign%n==0)cout<<endl;
cursor=cursor->next;
iEnterSign++;
}
if((iEnterSign-1)%n!=0)cout<<endl;
}
template <class T>int stack<T>::empty() //判断栈是否为空,1是,0非
{
return head==0?1:0;
}
template <class T>int stack<T>::sizeofstack() //返回栈的大小
{
int size=0;
link *cursor=head;
while(cursor)
{
cursor=cursor->next;
size++;
}
return size;
}
template<class T> void stack<T>:: clear() //清空栈
{
link *cursor=head;
while(cursor&&cursor->next)
{
cursor=cursor->next;
delete head;
head=cursor;
}
}
int Operator(char ch)
{
if(ch=='+'||ch=='-'||ch=='*'||ch=='/'||ch=='('||ch==')'||ch=='#')
return(TRUE);
else
return(FALSE);
}
char Precede(char ch1,char ch2)
{
char ch;
switch(ch1)
{
case '+':
case '-':
{
switch(ch2)
{
case '+':
case '-':
case ')':
case '#':
ch='>';break;
case '*':
case '/':
case '(':
ch='<';break;
}
break;
}
case '*':
case '/':
{
if(ch2=='(')
ch='<';
else
ch='>';
break;
}
case '(':
{
if(ch2==')')
ch='=';
else
ch='<';
break;
}
case ')':
{
ch='>';
break;
}
case '#':
{
if(ch2=='#')
ch='=';
else
ch='<';
break;
}
}
return(ch);
}
int calc(int x,char ch,int y)
{
int z;
switch(ch)
{
case '+': z=x+y; break;
case '-': z=x-y; break;
case '*': z=x*y; break;
case '/': z=x/y; break;
}
return(z);
}
int postexpression(char *exp)
{
stack<int> *opnd=new(stack<int>);
char ch=*exp;
int x=0,y,z,flag=FALSE;
int result;
while(ch!='#')
{
if(!Operator(ch))
{
if(ch!=' ')
{
x=x*10+(int)(ch)-48;
flag=TRUE;
}
else
{
if(flag)opnd->push(x);
x=0;
flag=FALSE;
}
}
else
{
x=opnd->pop();
y=opnd->pop();
z=calc(y,ch,x);
opnd->push(z);
}
ch=*(++exp);
}
result=opnd->pop();
return(result);
}
int middexpression(char *exp)
{
stack<int> *opnd=new(stack<int>);
stack<char> *optr=new(stack<char>);
char ch=*exp;
int x=0,y,z;
int result;
optr->push('#');
while(ch!='#'||optr->gettop()!='#')
{
if(!Operator(ch))
{
x=x*10+(int)(ch)-48;
if(Operator(*(exp+1)))
{
opnd->push(x);
x=0;
}
ch=*++exp;
}
else
{
switch(Precede(optr->gettop(),ch))
{
case '<'://栈顶元素优先权低
optr->push(ch);
ch=*++exp;
break;
case '='://脱括号并接收下一字符
optr->pop();
ch=*++exp;
break;
case '>'://退栈并将运算结果入栈
x=opnd->pop();
y=opnd->pop();
z=calc(y,optr->pop(),x);
opnd->push(z);
x=0;
break;
}
}
}
result=opnd->pop();
return(result);
}
void main(void)//程序入口函数
{
clock_t t1,t2,t3,t4;
int i,n=9000;
t1=clock();
for(i=0;i<n;i++)
postexpression("100 200 50 3 * - 13 8 - / +#");
//postexpression("100 200 50 8 45 9 / - - + #");
//postexpression("9 6 * 3 / 7 + 13 -#");
t2=clock();
printf("%10f\n",(t2-t1)/18.2/n);
t3=clock();
for(i=0;i<n;i++)
middexpression("100+(200-50*3)/(13-8)#");
//middexpression("100+(200-(50*(8-45/9)))#");
//middexpression("9*6/3+7-13#");
t4=clock();
printf("%10f\n",(t4-t3)/18.2/n);
printf("%10f",(t4-t3)/18.2/(t2-t1)*18.2);
cin.get();
参考资料:http://zhidao.baidu.com/question/14988945.html