arithmeticexpression.cpp

来自「数据结构的长数字算术表达式计算算法,包括加减乘除等」· C++ 代码 · 共 161 行

#define m 100
#include "stdio.h"
struct stack_optr{char s[m];int top;}optr;/*定义运算符栈*/
void create_optr(struct stack_optr *optr) /*建立运算符栈*/
{
	optr->top=-1;
}
int empty_optr(struct stack_optr *optr) /*判别运算符栈是否空*/
{
	return optr->top==-1?1:0;
}
int overflow_optr(struct stack_optr *optr) /*别运算符栈是否满*/
{
	return optr->top==m-1?1:0;
}
void clear_optr(struct stack_optr *optr) /*清空运算符栈*/
{
	optr->top=-1;
}
void push_optr(struct stack_optr *optr,char op) /*运算符入栈*/
{
	if(overflow_optr(optr))printf("overflow\n");
	else
	{
		optr->top++;
		optr->s[optr->top]=op;
	}
}
void pop_optr(struct stack_optr *optr,char *op) /*运算符出栈*/
{
	if(empty_optr(optr))printf("empty\n");
	else
	{
		*op=optr->s[optr->top];
		optr->top--;
	}
}
void gettop_optr(struct stack_optr *optr,char *op) /*取运算符栈顶元素*/
{
	if(empty_optr(optr))printf("empty\n");
	else *op=optr->s[optr->top];
}

struct stack_opnd{int s[m];int top;}opnd; /*定义操作数栈*/
void create_opnd(struct stack_opnd *opnd) /*建立操作数栈*/
{
		opnd->top=-1;
}
int empty_opnd(struct stack_opnd *opnd) /*判别操作数栈是否空*/
{
	return opnd->top==-1?1:0;
}
int overflow_opnd(struct stack_opnd *opnd) /*判别操作数栈是否满*/
{
	return opnd->top==m-1?1:0;
}
void clear_opnd(struct stack_opnd *opnd) /*清空操作数栈*/
{
	opnd->top=-1;
}
void push_opnd(struct stack_opnd *opnd,int x) /*操作数入栈*/
{
	if(overflow_opnd(opnd))printf("overflow\n");
	else
	{
		opnd->top++;
		opnd->s[opnd->top]=x;
	}
}
void pop_opnd(struct stack_opnd *opnd,int  *y) /*操作数出栈*/
{
	if(empty_opnd(opnd))printf("empty\n");
	else
	{
		*y=opnd->s[opnd->top];
		opnd->top--;
	}
}
void gettop_opnd(struct stack_opnd *opnd,int  *y) /*取操作数栈顶元素*/
{
	if(empty_opnd(opnd))printf("empty\n");
	else *y=opnd->s[opnd->top];
}
int getpriority(char ch)/*取得优先数*/
{
	int priority;
	switch(ch)
	{
	case '*':priority= 2;break;
	case '/':priority= 2;break;
	case '+':priority= 1;break;
	case '-':priority= 1;break;
	case '#':priority= 0;break;
	}
	return priority;
}
int isnumber(char ch)/*判别是否为数字*/
{
	if(ch<='9'&&ch>='0')return 1;
	else return 0;
}
void caculate(int x1,char op,int x2,int *x)/*根据运算符计算*/
{
	switch(op)
	{
	case '*':*x=x1*x2;break;
	case '/':*x=x1/x2;break;
	case '+':*x=x1+x2;break;
	case '-':*x=x1-x2;break;
	}
}

int getvalue(char *str)/*计算表达式*/
{
	char w,ch,op;	/*w用于存放当前字符，ch用于存放当前操作符栈栈顶符号，op用于存放当前运算的符号*/
	int index=1,x1,x2,x;/*index当前字符位置，x1操作数一，x2操作数二,x结果*/
	create_optr(&optr);	create_opnd(&opnd);/*建立操作符栈和操作数栈*/
	push_optr(&optr,'#');
	w=str[index];/*取当前字符*/
	gettop_optr(&optr,&ch);/*取当前操作符栈栈顶符号*/
	while(!((w=='#')&&(ch=='#')))/*当没有结束时*/
	{
		if(isnumber(w))/*是操作数*/
		{
			x=0;
			while(isnumber(w))
			{
				x=x*10+w-'0';
				index++;
				w=str[index];
			}
			push_opnd(&opnd,x);/*将操作数入操作数栈*/
		}
		else if((x1=getpriority(w))>(x2=getpriority(ch)))/*w优先于ch*/
		{
			push_optr(&optr,w);/*把w入操作符栈*/
			index++;
		}
		else /*ch优先于w*/
		{
			pop_optr(&optr,&op);/*操作符*/
			pop_opnd(&opnd,&x2);/*操作数2*/
			pop_opnd(&opnd,&x1);/*操作数1*/
			caculate(x1,op,x2,&x);/*计算*/
			push_opnd(&opnd,x);/*把结果入操作数栈*/
		}
		w=str[index];
		gettop_optr(&optr,&ch);
	}
	pop_opnd(&opnd,&x);
	return x;/*返回结果*/
}
void main()
{
	char str[m];int x;
	printf("please input an expression(start of #,end of #):\n");
	scanf("%s",str);
	x=getvalue(str);
	printf("%d",x);
}