主题：表达式求值（原创）
hoodbar
[专家分：0] 发布于 2006-12-13 20:00:00
#include <stdio.h>
#include <conio.h>
#include <malloc.h>
#include <stdlib.h>
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
typedef int Status;
#define STACK_INIT_SIZE 100 //初始分配量
#define STACKINCREMENT 10 //存储空间的分配增量
typedef char ElemType;
typedef ElemType OperandType; //操作数
typedef char OperatorType;
typedef struct
{
ElemType *base;
ElemType *top;
int stacksize;
}SqStack;
Status InitStack(SqStack &S)
{
//构造一个空栈S
S.base = (ElemType *)malloc(STACK_INIT_SIZE * sizeof(ElemType));
if(!S.base) exit (OVERFLOW);
S.top = S.base;
S.stacksize = STACK_INIT_SIZE;
return OK;
}
Status GetTop(SqStack S){
ElemType e;
if (S.top == S.base) return ERROR;
e = *(S.top-1);
return e;
}
Status Push (SqStack &S,ElemType e)
{
//插入元素e为新的栈顶元素
if (S.top - S.base >= S.stacksize){
S.base = (ElemType *) realloc ( S.base,
(S.stacksize + STACKINCREMENT) * sizeof(ElemType));
if(!S.base) exit (OVERFLOW);
S.top = S.base + S.stacksize;
S.stacksize += STACKINCREMENT;
}
*S.top++ = e;
return OK;
}
Status Pop (SqStack &S,ElemType &e){
//若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERROR
if(S.top == S.base) return ERROR;
e = * --S.top;
return OK;
}
char In(char c,char OP[])
{
if(c>=35 && c<=47)
return 1;
else return 0;
}
char OP[8]={'+','-','*','/','(',')','#','\0'};
int m[7][7]={1,1,2,2,2,1,1,
1,1,2,2,2,1,1,
1,1,1,1,2,1,1,
1,1,1,1,2,1,1,
2,2,2,2,2,0,-1,
1,1,1,1,-1,1,1,
2,2,2,2,2,-1,0};//1 > 2 < 0 = -1 不存在
char Precede(char i,char j)
{
int a,b; char *p;
for(p=OP,a=0;*p!='\0';p++,a++)
if(*p==i) break;
for(p=OP,b=0;*p!='\0';p++,b++)
if(*p==j) break;
if(m[a][b]==1) return '>';
else if(m[a][b]==2) return '<';
else if(m[a][b]==0) return '=';
else return 'O';
}
char Operate(char a,char theta,char b)
{
if(a>47) a=atoi(&a);
if(b>47) b=atoi(&b);
switch(theta)
{
case '+': return a+b;
break;
case '-': return a-b;
break;
case '*': return a*b;
break;
case '/': return a/b;
break;
}
}
OperandType EvaluateExpression()
{
SqStack OPTR,OPND;
OperandType a,b,c; OperatorType theta;
InitStack(OPTR); Push(OPTR,'#');
InitStack(OPND); c=getchar();
while (c!='#' || GetTop(OPTR)!='#')
{
if (!In(c,OP)){Push(OPND,c);c=getchar();}
else
switch(Precede(GetTop(OPTR),c))
{
case '<' :
Push(OPTR,c); c = getchar();
break;
case '=' :
Pop(OPTR,c); c = getchar();
break;
case '>' :
Pop(OPTR,theta);
Pop(OPND,b); Pop(OPND,a);
Push(OPND,Operate(a,theta,b));
break;
}
}
return GetTop(OPND);
}
void main()
{
printf("(以#为结束符)\n");
printf("请输入：\n");
int a;
a=(int)EvaluateExpression();
printf("%d",a);
getch();
}
回复列表 （共21个回复）
11 楼
hqin6 [专家分：140] 发布于 2006-12-14 15:32:00
第二个头文件：
debug.h
**********************
class NoMen//异常类
{
public:
NoMen(){}
protected:
private:
};
class OutOfBounds
{
public:
OutOfBounds(){}
protected:
private:
};
class BadInput
{
public:
BadInput(){}
};
12 楼
hqin6 [专家分：140] 发布于 2006-12-14 15:33:00
第三个头文件：
stack.h
****************************
#include "debug.h"
template <class T>
class Node
{
public:
T data;
Node<T> *link;
protected:
private:
};
template<class T>
class Stack
{
public:
Stack(){top=0;}
~Stack();
bool IsEmpty()const{return top==0;}
bool IsFull()const;
T Top()const;
Stack<T>& Add(const T&x);
Stack<T>&Delete(T&x);
protected:
private:
Node<T>*top;
};
template<class T>
Stack<T>::~Stack()
{
Node<T>*next;
while (top)
{
next=top->link;
delete top;
top=next;
}
}
template<class T>
bool Stack<T>::IsFull()const
{
try
{
Node<T> *p=new Node<T>;
delete p;
return false;
}
catch (NoMen)
{
return true;
}
}
template<class T>
T Stack<T>::Top()const
{
if(IsEmpty())throw OutOfBounds();
return top->data;
}
template<class T>
Stack<T>& Stack<T>::Add(const T&x)
{
Node<T>*p=new Node<T>;
p->data=x;
p->link=top;
top=p;
return *this;
}
template<class T>
Stack<T>&Stack<T>::Delete(T&x)
{
if (IsEmpty())throw OutOfBounds();
x=top->data;
Node<T>*p=top;
top=top->link;
delete p;
return *this;
}
13 楼
hqin6 [专家分：140] 发布于 2006-12-14 15:34:00
第四个头文件：
Node.h
*********************
template<class T> class LinkedQueue;
template <class T>
class LNode
{
friend LinkedQueue<T>;
public:
protected:
private:
T data;
LNode<T> *link;
};
14 楼
hqin6 [专家分：140] 发布于 2006-12-14 15:35:00
第五个头文件：
LinkedQueue.h
××××××××××××××
#include "Node.h"
template<class T>
class LinkedQueue
{
public:
LinkedQueue(){front=rear=0;}
~LinkedQueue();
bool IsEmpty()const{return ((front)?false:true);}
bool IsFull()const;
T First()const;
T Last()const;
LinkedQueue<T>&Add(const T&x);
LinkedQueue<T>&Delete(T&x);
protected:
private:
LNode<T>*front;
LNode<T>*rear;
};
template<class T>
LinkedQueue<T>::~LinkedQueue()
{
LNode<T> *next;
while (front)
{
next=front->link;
delete front;
front=next;
}
}
template<class T>
bool LinkedQueue<T>::IsFull()const
{
LNode<T>*p;
try
{
p=new LNode<T>;
delete p;
return false;
}
catch (NoMem)
{
return false;
}
}
template<class T>
T LinkedQueue<T>::First()const
{
if (IsEmpty())throw OutOfBounds();
return front->data;
}
template<class T>
T LinkedQueue<T>::Last()const
{
if (IsEmpty())throw OutOfBounds();
return rear->data;
}
template<class T>
LinkedQueue<T>&LinkedQueue<T>::Add(const T&x)
{
LNode<T>*p=new LNode<T>;
p->data=x;
p->link=0;
if (front)rear->link=p;
else front=p;
rear=p;
return *this;
}
template<class T>
LinkedQueue<T>&LinkedQueue<T>::Delete(T&x)
{
if (IsEmpty())throw OutOfBounds();
x=front->data;
LNode<T> *p=front;
front=front->link;
delete p;
return *this;
}
15 楼
hqin6 [专家分：140] 发布于 2006-12-14 15:38:00
第六个头文件：
tree.h
×××××××××××××××××
#include <iostream>
#include <vector>
#include <string>
#include "stack.h"
#include "LinkedQueue.h"
#include "BinaryTreeNode.h"
using namespace std;
int PRI(char sign)//优先级的计算
{
if (sign=='*'||sign=='/'||sign=='%')return 2;
if(sign=='+'||sign=='-')return 1;
return 0;
}
template<class T>
class BinaryTree
{
public:
BinaryTree(){root=0;}
void InputBinaryTree();
void Show_BinaryTree();
void MakeTree(BinaryTreeNode<T>*left,BinaryTreeNode<T>*mid,BinaryTreeNode<T>*right);
void TreeCount();
void ShowFloor();
void DeleteTree();
protected:
private:
void DeleteNode(BinaryTreeNode<T>*p);
void ShowNode(BinaryTreeNode<T>*p,LinkedQueue<BinaryTreeNode<T>*>&myqueue);
T Count(BinaryTreeNode<T>*p);
void Print_BNode(BinaryTreeNode<T> *p, int c, vector<bool>& isend,bool RorL);
BinaryTreeNode<T> *root;
};
template<class T>
void BinaryTree<T>::DeleteTree()
{
cout<<"销毁所建的树:"<<endl<<endl;
Stack<BinaryTreeNode<T>*> node_stack;
DeleteNode(root);
}
template<class T>
void BinaryTree<T>::DeleteNode(BinaryTreeNode<T>*p)
{
if (!p)
{
return;
}
if (!p->LeftChild&&!p->RightChild)
{
cout<<"删除节点";
if (p->sign>=37&&p->sign<=47)
{
cout<<p->sign;
}
else cout<<p->data;
cout<<"!"<<endl;
delete p;
return;
}
DeleteNode(p->LeftChild);
p->LeftChild=0;
DeleteNode(p->RightChild);
p->RightChild=0;
DeleteNode(p);
p=0;
}
//***********************************
template<class T>
void BinaryTree<T>::MakeTree(BinaryTreeNode<T>*left,BinaryTreeNode<T>*mid,BinaryTreeNode<T>*right)
{
mid->LeftChild=left;
mid->RightChild=right;
left=right=0;
}
(待续)
16 楼
hqin6 [专家分：140] 发布于 2006-12-14 15:40:00
（接上面）
template<class T>
void BinaryTree<T>::InputBinaryTree()
{
cout<<"请输入您要计算的表达式:"<<endl;
string str;
cin>>str;
Stack<BinaryTreeNode<T>*>num_stack;
Stack<BinaryTreeNode<T>*>sign_stack;
int len=str.length();
for (int i=0;i<len;)
{
if (str[i]=='+'&&(i==0||str[i-1]=='('))
{
i++;
}
else if (str[i]>47&&str[i]<58||str[i]=='-'&&(i==0||str[i-1]=='('))
{
T num;
string one_num;
while (str[i]>47&&str[i]<58||str[i]=='-'&&(i==0||str[i-1]=='(')||str[i]=='.')
{
one_num.append(&str[i],1);
i++;
}
if(one_num=="-")
{
str.insert(i-1,"0",1);
i--;
len=str.length();
continue;
}
num=atof(&one_num[0]);
BinaryTreeNode<T>*r=new BinaryTreeNode<T>(num);
num_stack.Add(r);
}
else if (sign_stack.IsEmpty()||str[i]=='(')
{
BinaryTreeNode<T>*r=new BinaryTreeNode<T>(str[i],true);
sign_stack.Add(r);
i++;
}
else
{
if (str[i]==')')
{
BinaryTreeNode<T>* l,*r,*m,*mid;
while (sign_stack.Top()->sign!='(')
{
num_stack.Delete(r);
num_stack.Delete(l);
sign_stack.Delete(m);
MakeTree(l,m,r);
num_stack.Add(m);
}
sign_stack.Delete(mid);
i++;
}
else
{
int now=PRI(str[i]),s_top=PRI(sign_stack.Top()->sign);
if (now==s_top||now<s_top)
{
BinaryTreeNode<T>* l,*r,*m,*mid;
while((now==s_top||now<s_top))
{
num_stack.Delete(r);
num_stack.Delete(l);
sign_stack.Delete(m);
MakeTree(l,m,r);
num_stack.Add(m);
if(sign_stack.IsEmpty())break;
now=PRI(str[i]),s_top=PRI(sign_stack.Top()->sign);
}
mid=new BinaryTreeNode<T>(str[i],true);
sign_stack.Add(mid);
i++;
}
else if (now>s_top)
{
BinaryTreeNode<T>*r=new BinaryTreeNode<T>(str[i],true);
sign_stack.Add(r);
i++;
}
}
}
}
17 楼
hqin6 [专家分：140] 发布于 2006-12-14 15:41:00
（接上面）
while (!sign_stack.IsEmpty())
{
BinaryTreeNode<T>* l,*r,*m,*mid;
num_stack.Delete(r);
num_stack.Delete(l);
sign_stack.Delete(m);
MakeTree(l,m,r);
num_stack.Add(m);
}
if (!num_stack.IsEmpty())
{
num_stack.Delete(root);
}
}
//**************************************
template<class T>
void BinaryTree<T>::Show_BinaryTree()
{
vector<bool> bIsEnd;
bIsEnd.push_back(0);
cout<<"您所输入的树是：\n";
cout<<"Root:";
if (!root->LeftChild&&!root->RightChild)
{
cout<<root->data<<endl;
}
else
{
cout<<root->sign<<endl;
Print_BNode(root->LeftChild,1,bIsEnd,false);
bIsEnd[0]=1;
Print_BNode(root->RightChild,1,bIsEnd,true);
cout<<endl;
}
}
template<class T>
void BinaryTree<T>::Print_BNode(BinaryTreeNode<T> *p, int c, vector<bool>& isend,bool RorL)
{
if (!p)
{
return;
}
for(int j=0;j<c;j++)
{//─└├│
if(isend[j]==0)
if(j!=c-1)cout<<"│";
else cout<<"├";
else if(j!=c-1)cout<<" ";
else cout<<"└";
if(j!=c-1)cout<<" ";
else cout<<"─";
}
if (!p->LeftChild&&!p->RightChild)
{
cout<<" "<<p->data;
}
else
cout<<" "<<p->sign;
if (RorL)
{
cout<<"R";
}
else cout<<"L";
cout<<endl;
for(int i=0;i<2;i++)
{
if(isend.size()==c)isend.push_back(0);
else isend[c]=0;
if(i==1)
{
if(isend.size()==c)isend.push_back(1);
else isend[c]=1;
}
if (i==0)
{
Print_BNode(p->LeftChild,c+1,isend,false);
}
else Print_BNode(p->RightChild,c+1,isend,true);
}
}
template<class T>
void BinaryTree<T>::TreeCount()
{
T result=Count(root);
cout<<"运算结果为：\n"<<result<<endl;
}
（待续）
18 楼
hqin6 [专家分：140] 发布于 2006-12-14 15:42:00
（接上面）
template<class T>
T BinaryTree<T>::Count(BinaryTreeNode<T>*p)
{
if (!p->LeftChild&&!p->RightChild)
{
return p->data;
}
T result,l=Count(p->LeftChild),r=Count(p->RightChild);
if (p->sign=='+')
{
return l+r;
}
else if (p->sign=='-')
{
return l-r;
}
else if (p->sign=='*')
{
return l*r;
}
else if (p->sign=='/')
{
if(r==0) throw BadInput();
return l/r;
}
else if (p->sign=='%')
{
return l%r;
}
else
{
cout<<"不支持"<<p->sign<<"运算"<<endl;
exit(1);
}
}
template<class T>
void BinaryTree<T>::ShowFloor()
{
LinkedQueue<BinaryTreeNode<T>*>myqueue;
int floor=1;
cout<<"遍历这棵二叉树：\n";
ShowNode(root,myqueue);
cout<<endl;
}
template <class T>
void BinaryTree<T>::ShowNode(BinaryTreeNode<T>*p,LinkedQueue<BinaryTreeNode<T>*>&myqueue)
{
if(p)
{
if (!p->LeftChild&&!p->RightChild)
{
cout<<" "<<p->data;
}
else
cout<<" "<<p->sign;
myqueue.Add(p->LeftChild).Add(p->RightChild);
}
if (myqueue.IsEmpty())
{
return;
}
BinaryTreeNode<T>*mid;
myqueue.Delete(mid);
ShowNode(mid,myqueue);
}
19 楼
hqin6 [专家分：140] 发布于 2006-12-14 15:43:00
主函数
main.cpp
××××××××××
#include "tree.h"
void Pause()
{
cout<<endl<<endl<<endl;
system("pause");
cout<<endl<<endl<<endl;
}
void main()
{
try
{
BinaryTree<int>mytree;
mytree.InputBinaryTree();
Pause();
mytree.Show_BinaryTree();
Pause();
mytree.TreeCount();
Pause();
mytree.ShowFloor();
Pause();
mytree.DeleteTree();
Pause();
}
catch (OutOfBounds)
{
cout<<"越界!"<<endl;
}
catch (BadInput)
{
cout<<"输入有误!"<<endl;
}
}
20 楼
Czhxdong [专家分：510] 发布于 2006-12-23 16:19:00
大牛,帮我看一下程序:
M0002 素数的个数
新闻发布: jhy 发布日期：2006年11月23日15:30 Submit：141 AC：23
题目描述：
老师给flyioi计算机组的同学出了一个问题：要求n以内的素数个数。可同学们都非常不屑于做这种easy problem，要来点挑战。于是老师顺手将n改为不大于30000000的正整数。这可难倒了大多数同学，大家都开动脑筋想算法。ZZZ不希望别人比他先做出来，可他自己不会啊！于是他向聪明的你求助。
输入格式：
一个数，n
输出格式：
一个数，n以内的素数个数
样例输入：
120
样例输出：
30
#include<stdio.h>
#include<math.h>
#include<stdlib.h>
void main()
{FILE *in,*out;
long i,j,k,n,m,mm,nn;
long num=0,prime=0,leap1=1,leap2=1;
long *pr;
in=fopen("zhxdong.in","r");
fscanf(in,"%ld",&n);
fclose(in);
nn=(long)sqrt(n);
pr=(long *)malloc(nn*sizeof(long));
for(i=2;i<=nn;i++)
{ mm=(long)sqrt(i);
for(j=2;j<=mm;j++)
if(i%j==0 && i!=j)
leap1=0;
if(leap1)
pr[num++]=i;
leap1=1;
}
for(m=2;m<=n;m++)
{
for(k=0;k<num;k++)
if(m%pr[k]==0 && m!=pr[k])
leap2=0;
if(leap2)
prime++;
leap2=1;
}
out=fopen("zhxdong.out","w");
fprintf(out,"%ld",prime);
fclose(out);
free(pr);
}
我来回复
您所在位置：