STL 스 택 (링크 구현)

1. 실험 프로젝트 2 스 택 의 기본 조작 과 응용
마감 시간: 11 월 17 일 23: 59 과정 명칭: 데이터 구조 실험 목적: 1. 스 택 의 정의 와 실현 파악;2. 스 택 을 이용 하여 산술 표현 식 을 푸 는 방법 을 파악 한다.실험 요구: 1. 체인 저장 구 조 를 사용 하여 스 택 의 각종 기본 작업 을 완성 합 니 다.2. 보충 완성 In©, Preced (t1, t2), Operate (a, theta, b) 세 가지 함수.실험 문제: 스 택 의 기본 조작 과 응용 실험 과정: 1. 교재 중의 알고리즘 을 수정 하고 보완 하 며 스 택 을 이용 하여 산술 표현 식 의 값 을 구 하 는 알고리즘 을 실현 합 니 다.알고리즘 3.22 에서 호출 된 몇 가지 함수 에 대해 실현 과정 을 제시 해 야 합 니 다. (1) 함수 In©：c 가 연산 자인 지 판단 하기;(2) 함수 Precede (t1, t2): 연산 자 t1 과 t2 의 우선 순 위 를 판단 합 니 다.(3) 함수 Operate (a, theta, b): a 와 b 를 이원 연산 theta.2. 프로그램 이 실 행 될 때 합 법 적 인 산술 표현 식 (중간 값 과 최종 결 과 는 0 ~ 9 사이 이 고 덧셈 과 괄호 포함) 을 입력 하면 해당 하 는 계산 결 과 를 출력 할 수 있 습 니 다.실험 알림: (참고 로 모든 함수 의 구체 적 인 실현 은 여러 가지 방법 이 있 을 수 있 습 니 다. 혁신 이 있 기 를 바 랍 니 다)

스 택 의 정의 와 구현 을 헤더 파일 'stack. h' 에 따로 저장 한 다음 표현 식 에서 값 을 구 하 는 소스 프로그램 에 이 헤더 파일 (즉, \ # include 'stack. h') 을 포함 합 니 다.2. 표현 식 값 원본 프로그램의 구체 적 인 실현 (1) 주 함 수 는 다음 과 같다. void main () {Printf ("산술 표현 식 을 입력 하고 \ # 로 끝내 십시오."); Printf ("the result of expression is:% d", Evaluate Expression ();} (2) 함수 Evaluate Expression 의 실현 알고리즘 3.22 (3) 함수 In©의 실현 은 다음 과 같은 방식 을 사용 할 수 있 습 니 다. Status In (SElemType c) / / 앞에서 typedef char SElemType 을 정의 해 야 합 니 다.{/ / c 가 연산 자 switch 인지 판단© {case '+': return TRUE;... / 완전 default: return FALSE;} (4) 함수 Precede (t1, t2) 의 실현 은 다음 과 같은 형식 으로 할 수 있 습 니 다: SElemType Precede (SElemType t1, SElemType t2) {/ 교재 표 3.1 에 따라 두 연산 자의 우선 관 계 를 판단 합 니 다 SElemType f; switch (t2) {case '+': case '-': if (t1 = = '\ #')f = 'else f =' > '; break;... / 완전 보충} return f;} (5) 함수 Operate (a, theta, b) 의 실현 은 다음 과 같은 방식 을 사용 할 수 있 습 니 다: SElemType Operate (SElemType a, SElemType theta, SElemType b) {SElemType c; a = a - 48; b = b - 48; switch (theta) {case' +: c = a + b + 48; break;.... / 완전 보충} return c;}

선택 내용: 표현 식 의 중간 값 과 최종 결 과 를 0 ~ 9 사이 의 한 자릿수 에 국한 되 지 않도록 개선 합 니 다. (완성 되면 실험 보고서 에 표시) 다음 그림: 실험 결과: 입력: 2 * (4 - 1)+ 8 출력: 14 이 프로그램 은 한 자릿수 의 네 가지 연산 을 완성 할 수 있 습 니 다. 실험 분석: 1. 스 택 의 작업 특징, 2. 디 버 깅 실행 과정 에서 발생 하 는 오 류 를 열거 하고 원인 을 분석 합 니 다. 요구: (1) 프로그램 은 적당 한 주석 을 추가 하고 프로그램의 작성 은 들 여 쓰기 형식 을 사용 해 야 합 니 다. (2)프로그램 은 일정한 건장 성 을 가 져 야 한다. 즉, 입력 데이터 가 불법 일 때 프로그램 도 적절하게 반응 할 수 있다. (3) 프로그램 은 인터페이스 가 우호 적 이 어야 하 며, 프로그램 이 실 행 될 때 사용 자 는 해당 하 는 알림 정보 에 따라 조작 할 수 있다. (4) 원본 프로그램 을 교실 파 에 업로드 하고, 원본 순 서 는 calculator. cpp 로 저장 해 야 한다.
1 창고 의 실현

#pragma GCC optimize(2)
//#include
#include
//#include
#include

using namespace std;
#define pi acos(-1.0)
#define e exp(1.0)
typedef long long ll;//     ,            
struct Lnode 
{
	ll date;//            
	Lnode *next;
};
struct Sqlist 
{
	Lnode *head;
	ll size;
}List;
void init()
{
	List.head=NULL;//head        
	List.size=0;
	return ;
}
bool empty()
{
	if(List.size==0)
	return true;
	return false;
}
void push(ll n)
{
	Lnode *pos=new Lnode;
	pos->date=n;
	if(List.size==0)
	pos->next=NULL;
	else
	pos->next=List.head;
	List.head=pos;
	List.size++;
	return ;
}
ll top()
{
	if(empty())
	{
		cout<<"   ,     "<<endl;
		return -1;
	}
	return List.head->date;
}
void pop()
{
	if(empty())
	{
		cout<<"   ,     "<<endl;
		return ;
	}
	Lnode *pos=List.head;
	List.head=pos->next;
	delete pos;
	List.size--;
	return ;
}
ll size()
{
	return List.size;
}
int main()
{
//	freopen(".../.txt","w",stdout);
//	ios::sync_with_stdio(false);
	ll i,j;
	ll N;
	while(cin>>N)
	{
		init();
		for(i=0;i<N;i++)
		{
			ll n;
			cin>>n;
			push(n);
		}
		while(!empty())
		{
			ll n=top();
			pop();
 			cout<<n<<' ';
		}
		cout<<endl;
	}
	return 0;
}

1 창고 로 기본 산술 연산 실현

#pragma GCC optimize(2)
#include

using namespace std;

#define pi acos(-1.0)
#define e exp(1.0)
typedef long long ll;//        ,                
const ll maxn=300;
string S,s;
string suffix[maxn],infix[maxn];//              
ll sulen,inlen;
ll Tran(string s)
{
	ll sum=0,i,j;
	for(i=0;i<s.length();i++)
	sum=sum*10+s[i]-'0';
	return sum;
}
void Suffix_Infix()//                 
{
	ll i,j;
	stack<string>sta;
	inlen=0;
	for(i=0;i<sulen-1;i++)//               
	{
		if(suffix[i].length()==1)//          
		{
			if(suffix[i][0]=='+'||suffix[i][0]=='-')
			{
				while(!sta.empty())//           
				{
					string jie=sta.top();
					if(jie[0]=='(')
					break;
					infix[inlen++]=jie;
					sta.pop();
				}
				sta.push(suffix[i]);
			}
			else if(suffix[i][0]=='*'||suffix[i][0]=='/')
			{
				while(!sta.empty())//           
				{
					string jie=sta.top();
					if(jie[0]=='('||jie[0]=='+'||jie[0]=='-')
					break;
					infix[inlen++]=jie;
					sta.pop();
				}
				sta.push(suffix[i]);
			}
			else if(suffix[i][0]=='(')
			sta.push(suffix[i]);
			else if(suffix[i][0]==')')//   )   (          
			{
				while(!sta.empty())
				{
					string jie=sta.top();
					if(jie[0]=='(')
					{
						sta.pop();
						break;
					}
					infix[inlen++]=jie;
					sta.pop();
				}
			} 
			else//        
			infix[inlen++]=suffix[i];			
		}
		else
		infix[inlen++]=suffix[i];//            
	}
	while(!sta.empty())//          infix  
	{
		infix[inlen++]=sta.top();
		sta.pop();
	}
	return ;
}
double Eva(string *infix)
{
	stack<double>Jie;
	ll i,j;
	for(i=0;i<inlen;i++)//           
	{
		if(infix[i][0]>='1'&&infix[i][0]<='9')
		{
			double sum=double(Tran(infix[i]));
			Jie.push(sum);
		}
		else
		{
			double sum=Jie.top();
			Jie.pop();
			double Sum=Jie.top();
			Jie.pop();
			if(infix[i][0]=='+')
			Sum+=sum;
			else if(infix[i][0]=='-')
			Sum-=sum;
			else if(infix[i][0]=='*')
			Sum*=sum;
			else if(infix[i][0]=='/')
			Sum/=sum;
			Jie.push(Sum);
		}
	}
	double sum=Jie.top();
	Jie.pop();
	return sum;
}
int main()
{
//	freopen(".../.txt","w",stdout);
	ios::sync_with_stdio(false);
	cout<<"      :(             )"<<endl;
	while(cin>>S)
	{
		ll i,j;
		s="";
		for(i=0;i<S.length();i++)//            
		{
			if(S[i]=='+'||S[i]=='-'||S[i]=='*'||S[i]=='/'||S[i]=='('||S[i]==')')
			{
				s+=' ';
				s+=S[i];
				s+=' ';
			}
			else
			s+=S[i];
		}
		sulen=0;
		stringstream ss(s);
		while(ss>>suffix[sulen++]);//          
		Suffix_Infix();
		cout<<"    :"<<endl;
		cout<<Eva(infix)<<endl;
	} 
	return 0;
}