stackexpr.cpp

数据结构

// StackExpr.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include "iostream.h"
#include "stdlib.h"

#define  SIZE 50

typedef struct{
	int   opnd_stack[SIZE];
	int   opnd_top;
}stack_nd;

typedef struct {
	char optr_stack[SIZE];
	int  optr_top;
}stack_tr;

bool init_opnd_stack(stack_nd * s){
	s->opnd_top=-1;
	return true;
}

bool init_optr_stack(stack_tr *s){
	s->optr_top=0;
	return true ;
}

void nd_push_stack(stack_nd *s,int x)    /*数入栈操作*/
{
 	if (s->opnd_top==SIZE-1)
    {
		printf("the stack is overflow!\n"); 
		exit(0);
	}
  	else
  	{
  		s->opnd_top=s->opnd_top+1;
		s->opnd_stack[s->opnd_top]=x;
  	}
}

void tr_push_stack(stack_tr *s,char x)    /*数入栈操作*/
{
 	if (s->optr_top==SIZE)
	{
		printf("the string stack is overflow!\n");
		exit(0);  
	}
  	else
  	{
		s->optr_top=s->optr_top+1;
	    s->optr_stack[s->optr_top]=x;
   	}
}

int nd_pop_stack(stack_nd *s)	/*出栈操作并返回被删除的那个记录*/
{
 	int y;
  	if(s->opnd_top==-1)
  	{  
		printf("the stack is empty!\n"); 
		return 0;
	}
  	else
  	{
  		y=s->opnd_stack[s->opnd_top];
  		s->opnd_top=s->opnd_top-1;
  		return y;
  	}
}

char tr_pop_stack(stack_tr *s)
{
	char c;
	if(s->optr_top==0) 
	{	
		printf("the stack is empty!\n");
		return 0;
	}
	else
	{
    	c=s->optr_stack[s->optr_top];
		s->optr_top=s->optr_top-1;
		return c;
	}
}
 
int nd_gettop(stack_nd *s)  /*得到栈顶数*/
{
 	int e;
  	if(s->opnd_top==-1)
  		return 0;
  	else
  		e=s->opnd_stack[s->opnd_top];
  	return e;
}
  
char tr_gettop(stack_tr *s)  /*得到栈顶数*/
{
 	char e;
  	if(s->optr_top==0)
  		return NULL;
  	else
  		e=s->optr_stack[s->optr_top];
  	return e;
}

//判断是否是数字函数in()
bool in(char r)
{
    if (r>'/' && r< ':') 
		return false;//ASCII在'/'和':'之间的是数字
    else  
		return true ;
}
 
char precede(stack_tr *s,char t,char r)
{//判断优先函数precede()
    char th;
    th=t;
	if(th=='+'||th=='-')
	{//遇到右括号，前面的符号优先级都高
		switch (r)
		{
            case '+' :
            case '-' :return '>';
            case '*' :
            case '/' :
            case '(': return '<';
			//加减后面遇到乘除，由于乘除的后面运算数还未读出，故仍旧直接压入
            case ')':return '>';
            case '#':return '>';
		}
	}
    if(th=='*'||th=='/')
	{//乘除后面遇到加减，乘除优先级要更高，直接运算乘除
		switch (r)
		{
            case '+' :
            case '-' :return '>';
            case '*' :
            case '/' : return '>';
            case '(' :return  '<';
            case ')' :return '>';
            case '#':return '>';
         }
	}
    if(th=='(' )
	{
		switch (r)
		{
            case '+' :
            case '-' :
            case '*' :
            case '/' :
            case '(' :return  '<';
            case ')' :return '=';
		}
	}
    if(th==')' )
	{
		switch (r)
		{
            case '+' :
            case '-' :
            case '*' :
            case '/' :return  '>';
        }
	}
    if(th=='#')
	{ 
		switch(r)
		{
            case '+' :
            case '-' :
            case '*' :
            case '/' :
            case '(' :
            case ')' : return '<';
        }
	}
    return NULL;
}
 
int operation(int n,char c,int m)
{
    switch(c)
	{
        case '+': return n+m;
        case '-': return n-m;
        case '*': return n*m;
        case '/': return n/m;
    }
    return 0;
}
//运算函数operation

int Evaluateexpression(stack_nd *nds,stack_tr *trs)
{
	char c;
	char ch;
	int a,b;
    char chr;
    bool tag1=false;
    bool tag2=false;
	init_opnd_stack(nds);
	init_optr_stack(trs);
	tr_push_stack(trs,'#');
	c=getchar();

	while(!NULL)//输入字符非NULL
	{//in 表示数字函数
		if(!in(c))//如果是数字 
		{
			nd_push_stack(nds,'*');
			nd_push_stack(nds,c-'0');//数字字符化为数字值
			c=getchar();
			while(!in(c)){
			   nd_push_stack(nds,c-'0');
			   c=getchar();
			}
			int a = nd_pop_stack(nds);
			int n = 1;
			int num = 0;
			while(a!='*'){
			   num = a*n + num;
			   n = n*10;
			   a = nd_pop_stack(nds);
			}
			nd_push_stack(nds,num);
		}
		else
		{
			switch(precede(trs,tr_gettop(trs),c))
			{
				case '<':
					tr_push_stack(trs,c);
					c=getchar();break;
				case '='://括号中的值求出后，遇到右括号时将左括号弹出
					tr_pop_stack(trs);
					c=getchar();break;
				case '>':
				    ch=tr_pop_stack(trs);
				    b=nd_pop_stack(nds);
					a=nd_pop_stack(nds);
				    nd_push_stack(nds,operation(a,ch,b));
					if((chr=tr_pop_stack(trs))=='#'&&c=='#')
					{
						tag1=true;  
						break;//tag1标记以正确结果跳出switch
					}
					else
					    tr_push_stack(trs,chr);
			}
            if(tag1==true) 
			{
				tag2=true;
				break;//tag2标记正确跳出while循环
			}
		}
	}//while
    if(tag2==true)
		return nd_pop_stack(nds);
    else return 0;
}//主运算函数

void main()
{
	stack_nd nd;
    stack_tr tr;
    stack_nd *nd1;
    stack_tr *tr1;
    nd1=&nd;
	tr1=&tr;
    int num;

	/*char choice='y';
	while(1)
	{
		if(choice=='y')
		{
		   printf("请输入一个表达式包括+'-'*'\'( ' ) 并以#结束\n");
           num=Evaluateexpression( nd1,tr1);
           cout<<num<<endl;
		}
		if(choice=='n')
		{
		     printf("谢谢使用！");
			 break;
		}
		printf("是否继续运算？请输入y/n。\n");
		choice=getchar();
	}*/
    printf("请输入一个表达式包括+'-'*'\'( ' ) 并以#结束\n");
	num=Evaluateexpression( nd1,tr1);
	cout<<num<<endl;
}