算术表达式求值演示,具体的实现和演示,很好的算法,最基础的数据结构内容

#include "stdafx.h"
#include<iostream>
#include<process.h>
#include<malloc.h>
#include<cstdlib>


using namespace std;

#define STACK_INIT_SIZE  100
#define STACKINCREMENT   10

typedef char SElemType1   ;    //输入的数据类型1
typedef int SElemType2   ;     //输入的数据类型2




//链表
typedef struct{
    char *elem;
    int length;
    int listsize;
}SqList;

bool InitList(SqList &L)    //建立空链表
{
    L.elem=(char *)malloc(STACK_INIT_SIZE*sizeof(char));
    if(!L.elem)exit(0);
    L.length=0;
    L.listsize=STACK_INIT_SIZE;
    return 1;
}

bool ListEmpty(SqList L)    //判定链表是否空,空则返回1
{
	return L.length==0 ? 1 : 0;
}

int ListLength(SqList L)    //返回链表长度
{
	return L.length;
}

bool ListInsert(SqList &L,int i,char e)    //在第i个位置之前插入新的数据元素e,表长加1
{
	if(i<1||i>L.length+1)
		return 0;
	if(L.length>=L.listsize)
	{
		char *newbase=(char*)realloc(L.elem,(L.listsize+STACKINCREMENT)*sizeof(char));
		if(!newbase)exit(0);
		L.elem=newbase;
		L.listsize+=STACKINCREMENT;
	}
	char* q=&(L.elem[i-1]);
	for(char *p=&(L.elem[L.length-1]);p>=q;--p)*(p+1)=*p;
	*q=e;
	++L.length;
	return 1;
}

void DisplayList(SqList L,int i)    //逐个字符输入
{
	cout<<"输入字符:";
	for(int v=i;v<L.length;v++)
	{
		cout<<L.elem[v];
	}
       	cout<<"\n";
}
 



//操作符栈
typedef struct{
	SElemType1	*base;
	SElemType1	*top;
	int			stacksize;
}SqStack1;


bool InitStack(SqStack1 &s)    //构造空栈
{
	s.base=(SElemType1 *)malloc(STACK_INIT_SIZE * sizeof(SElemType1));
	if(!s.base)exit(0);
	s.top=s.base;
	s.stacksize=STACK_INIT_SIZE;
	return 1;
}

bool GetTop(SqStack1 s,SElemType1 &e)    //返回栈顶元素给e，同时有判断栈是否为空的功能，空则返回0
{
	if(s.top==s.base)return 0;
	e=*(s.top-1);
	return 1;
}

bool Push(SqStack1 &s,SElemType1 e)    //插入元素e为新的栈顶元素
{
	if(s.top-s.base>=s.stacksize)
	{
		s.base=(SElemType1 *)realloc(s.base,(s.stacksize+STACKINCREMENT) * sizeof(SElemType1));
		if(!s.base)exit(0);
		s.top=s.base+s.stacksize;
		s.stacksize+=STACKINCREMENT;
	}
	*s.top++ =e;
	return 1;
}

bool Pop(SqStack1 &s,SElemType1 &e)    //删除栈顶元素并用e返回其值
{
	if(s.top==s.base)return 0;
	e=*--s.top;
	return 1;
}

void Display(SqStack1 &s,SElemType1 &p,int m)    //显示当前步骤数
{

	cout<<"\n步骤"<<m<<":\n";
	SElemType1 *q=s.base;    //保留s.base
	cout<<"OPTR栈：";
	while(s.top!=s.base)
	{
		p=*s.base;  cout<<p;  s.base++;
	}
	s.base=q;    //还原s.base
	cout<<"\n";
}



//数字栈
typedef struct{
	SElemType2	*base;
	SElemType2	*top;
	int			stacksize;
}SqStack2;


bool InitStack(SqStack2 &s)    //构造空栈
{
	s.base=(SElemType2 *)malloc(STACK_INIT_SIZE * sizeof(SElemType2));
	if(!s.base)exit(0);
	s.top=s.base;
	s.stacksize=STACK_INIT_SIZE;
	return 1;
}

bool GetTop(SqStack2 s,SElemType2 &e)    //返回栈顶元素给e，同时有判断栈是否为空的功能，空则返回0
{
	if(s.top==s.base)return 0;
	e=*(s.top-1);
	return 1;
}

bool Push(SqStack2 &s,SElemType2 e)    //插入元素e为新的栈顶元素
{
	if(s.top-s.base>=s.stacksize)
	{
		s.base=(SElemType2 *)realloc(s.base,(s.stacksize+STACKINCREMENT) * sizeof(SElemType2));
		if(!s.base)exit(0);
		s.top=s.base+s.stacksize;
		s.stacksize+=STACKINCREMENT;
	}
	*s.top++ =e;
	return 1;
}

bool Pop(SqStack2 &s,SElemType2 &e)    //删除栈顶元素并用e返回其值
{
	if(s.top==s.base)return 0;
	e=*--s.top;
	return 1;
}



void Display(SqStack2 &s,SElemType2 &p)    //显示当前OPND栈内容
{
	SElemType2 *q=s.base;    //保留s.base
	cout<<"OPND栈：";
	while(s.top!=s.base)
	{
		p=*s.base;  cout<<p<<"  ";  s.base++;
	}
	s.base=q;    //还原s.base
	cout<<"\n";
}




char Precede(char a,char b)
{    //判断运算符的优先级
	if(a=='+'&&(b=='+'||b=='-'||b==')'||b=='#')||
	   a=='-'&&(b=='+'||b=='-'||b==')'||b=='#')||
	   a=='*'&&(b=='+'||b=='-'||b==')'||b=='#'||b=='*'||b=='/')||
	   a=='/'&&(b=='+'||b=='-'||b==')'||b=='#'||b=='*'||b=='/')||
	   a==')'&&(b=='+'||b=='-'||b==')'||b=='#'||b=='*'||b=='/'))
	   return '>';
	else if(a=='('&&b==')'||a=='#'&&b=='#')
		return '=';
	else
		return '<';
}



int Operate(int a,char theta,int b)    //四则运算
{
	int z=0;
	switch(theta)
	{
	case'+':
		z=a+b;
		break;
    case'-':
		z=a-b;
		break;
	case'*':
		z=a*b;
		break;
	case'/':
		if(b==0) {cout<<"除数为零，错误！！\n";  break;}
		if(a%b!=0) {cout<<"除不尽！！\n";  break;}
		z=a/b;
		break;
	}
	return z;
}




int EvaluateExpression(SqList L)
{    
	//算法表达式求值的算符优先算法。设OPTR为运算符栈，OPND为运算数栈。
	char theta,x,e1;
	int a,b,e2=0;
	int temp=0;    //暂存器，暂存计算结果
	int n=0;    //计数器，计算int型数据位数（如“8488”为4位）
	int i=0;    //用来控制"输入字符"项的输出
	int m=1;    //步骤数
	char r;
	int s;
	SqStack1 OPTR;  	InitStack(OPTR); Push(OPTR,'#');
	SqStack2 OPND;   InitStack(OPND);    

	while(GetTop(OPTR,e1))
	{
		if(L.elem[i]!='+'&&L.elem[i]!='-'&&L.elem[i]!='*'&&L.elem[i]!='/'&&L.elem[i]!='('&&L.elem[i]!=')'&&L.elem[i]!='#')
		{
			n++;  i++;
			Display(OPTR,r,m);m++;
		    Display(OPND,s); 
			DisplayList(L,i-1);
		}
		else
		{   
			if(n!=0)  
			{
				temp=atoi(&L.elem[i-n]);  Push(OPND,temp); 
				cout<<"主要操作:"<<"PUSH(OPND,'"<<temp<<"')\n";
			}
		   		    
		    n=0;    //计数器清零
			GetTop(OPTR,e1);
			
			switch(Precede(e1,L.elem[i])) 
		{
			  case'<':    //栈顶元素优先权低
				  Display(OPTR,r,m);m++;
		          Display(OPND,s);
				  DisplayList(L,i);
				  Push(OPTR,L.elem[i]);    //c=getchar();
				  cout<<"主要操作:"<<"PUSH(OPTR,'"<<L.elem[i]<<"')\n";
				  i++;
				  break;
			  case'=':    //脱括号并接受下一字符
				  Display(OPTR,r,m);m++;
		          Display(OPND,s); 
				  DisplayList(L,i);			      
				  Pop(OPTR,x);    
				  if(x=='(')
				  cout<<"主要操作:"<<"POP(OPTR){消去一对括号}\n";
				  else
				  cout<<"RETURN(GETTOP (OPND))\n";
				  i++;
				  
				  break;
			  case'>':    //退栈并将运算结果入栈
				  Display(OPTR,r,m);m++;
		          Display(OPND,s); 
				  DisplayList(L,i);
				  Pop(OPTR,theta);
				  Pop(OPND,b);  Pop(OPND,a);
				  Push(OPND,Operate(a,theta,b));  
				  cout<<"主要操作:"<<"operate('"<<a<<"','"<<theta<<"','"<<b<<"')\n";
				  break;   
				  
		}//switch

		}//else
	

}//while

	GetTop(OPND,e2);
	return e2;

}//EvaluateExpression





void main()
{
loop:
SqList L1;
 InitList(L1);
 char yuansu;    
 cout<<"==========2.5  算术表达式求值演示==========\n\n\n";
 cout<<"请输入正确的表达式并以“#”号结束：    （例如输入“3*(7-2)#”）\n";
 for(int i=1;;i++) 
 {
	cin>>yuansu;
	if(yuansu=='#') {ListInsert(L1,i,yuansu); break;}
	 ListInsert(L1,i,yuansu);
 }
cout<<"\nresult="<<EvaluateExpression(L1)<<"\n\n";
 cout<<"Run again? (y/n)";
 char again;
 cin>>again;
 if(again=='y') goto loop;
 else if(again=='n') exit(0);
}