首页 > 代码库 > 栈的应用举例-进行算术运算

栈的应用举例-进行算术运算

   这个例子是来自于严蔚敏的《数据结构》的栈那一节。 但是我进行了一些简单的修改,确保编译通过。

目的:利用栈 计算 “3*(7-2)”这样的字符串的算术运算的结果。 共有3个代码文件,如下:

1、mystack.h

       

#pragma once#define maxsize 30typedef struct{	char data[maxsize+1];    int top;}Stack;int Push(Stack& S,char x);int Pop(Stack& S,char& x);char readtop(Stack S);

 

2、mystack.cpp

#include "mystack.h"#include "stdio.h"int Push(Stack& S,char x){	if (S.top==maxsize)	{		printf("overflow\n"); 		return(0);	}	S.data[++S.top]=x; 	return(1);}int Pop(Stack& S,char& x){	if(S.top==0)	{		printf("undertflow\n");		return(0);	}	x=S.data[S.top]; 	S.top--;	return(1);}char readtop(Stack S){	char a;          a=S.data[S.top]; 	return(a);}

 

3、 caclstack.cpp

#include <iostream>#include <string>#include "mystack.h"using namespace std;double operate(char ch, double x,double y);int precede(char p1,char p2);double calcul(char a[]);
 
//这是进行测试的main 函数int main(){	char tmp[]="3*(7-2)#";  // 输入的字符串一定要以# 结尾。        // char tmp[]="3*(7-2)+5*2#";	double rst = calcul(tmp);	cout<<rst<<endl;	getchar();	return 0;}double operate(char ch, double x,double y){	double z;	switch (ch)	{	case '+' : z=x+y; break;	case '-' : z=x-y; break;	case '*' : z=x*y; break;	case '/' : z=x/y; break;	}	return((char)z);}//这个函数最关键int precede(char p1,char p2){	int flag = -2;	switch (p1)	{	case '+' : 		if(p2=='*' || p2=='/' || p2== '(' ) flag=-1;		else flag=1;		break;	case '-' : 		if(p2=='*' || p2=='/' || p2== '(' ) flag=-1;		else flag=1;		break;	case '*' : 		if(p2=='(' ) flag=-1;		else flag=1;		break;	case '/' : 		if(p2=='(' ) flag=-1;		else flag=1;		break;	case '(' : if(p2==')') flag=0;			   else if(p2=='#')printf("error 1 operator!\n");			   else flag=-1;			   break;	case ')' : if(p2=='(' )printf("error 2 operator!\n");			   else flag=1;			   break;	case '#' : if(p2==')' )printf("error 3 operator!\n");				else if(p2=='#' ) 					flag=0;				else 					flag=-1;				break;	}	return(flag);}double calcul(char a[]){	Stack S1, S2;	S1.top = 0; 	S2.top = 0;	double x, y, z;	char x1,x2;	char r, ch;	int I=0;	Push(S1,'#'); 	r=a[I];	//while(r<>'#' || readtop(S1)<>'#')	while(r != '#' || readtop(S1) != '#')	{		if(r<='9' && r>='0')		{ 			x=0;			while(r<='9' && r>='0')			{				x=x*10+r-'0';				r=a[++I];			}			Push(S2,x);		}		else 			switch(precede(readtop(S1),r))		{			case -1: 				Push(S1,r); r=a[++I]; break; //把运算符放进栈1			case 0:				Pop(S1,ch); 				r=a[++I];				//r=a[I];				break; //弹出一个运算符			case 1: 				Pop(S1, ch); Pop(S2, x1); Pop(S2, x2);				Push(S2,operate(ch, x2,x1));				//r=a[++I];                  r=a[I];				break;		}	}	return(readtop(S2));}


 

以上代码在VS 下编译通过,并且执行结果正确。

注意:本文的栈 是用的自定义 的mystack。

另外更多原理 请参考 严蔚敏的数据结构相关章节。