一、链栈实现栈混洗（出栈顺序合法性）

#include <iostream>
using namespace std;

const int maxn = 1005;
char str[maxn], cmp[maxn];
template<typename T>
struct Node{
	T data;
	Node<T> *Next;
};

template<typename T>
class LinkStack{
	private:
		int size_;
		Node<T> *head;
	public:
		LinkStack(){
			size_ = 0;
			head = new Node<T>;
			head->Next = NULL;
		}
		
		void Push(T e){
			Node<T> *pNode = new Node<T>;
			pNode->data = e;
			pNode->Next = head->Next;
			head->Next = pNode;
			size_++;
		}
		
		void Pop(){
			Node<T> *pNode = head->Next;
			head->Next = pNode->Next;
			delete pNode;
			size_--;
		}
		
		T Top(){
			return head->Next->data;
		}
		
		bool Empty(){
			return 0 == size_;
		}
};

bool isValid(int n){
	int pos = 0;
	LinkStack<char> s;
	for(int i = 0;i < n;i++){
		if(str[i] == cmp[pos]){
			pos++;
			while(!s.Empty() && s.Top() == cmp[pos]){
				pos++;
				s.Pop();
			}
		}
		else
			s.Push(str[i]);
	}
	return s.Empty();
}

int main(){
	int n;
	while(cin >> n && n){
		for(int i = 0;i < n;i++)	
			cin >> str[i];
		for(int i = 0;i < n;i++)
			cin >> cmp[i];
		if(isValid(n))
			cout << '1' << endl;
		else
			cout << '0' << endl;
	}
	return 0;
}

二、求中缀表达式的值

#include <iostream>
#include <string>
using namespace std;

template<typename T>
struct Node{
	T data;
	Node<T> *Next;
};

template<typename T>
class LinkStack{
	private:
		int size_;
		Node<T> *head;
	public:
		LinkStack(){
			size_ = 0;
			head = new Node<T>;
			head->Next = NULL;
		}
		
		void Push(T e){
			Node<T> *pNode = new Node<T>;
			pNode->data = e;
			pNode->Next = head->Next;
			head->Next = pNode;
			size_++;
		}
		
		void Pop(){
			Node<T> *pNode = head->Next;
			head->Next = pNode->Next;
			delete pNode;
			size_--;
		}
		
		T Top(){
			return head->Next->data;
		}
		
		bool Empty(){
			return 0 == size_;
		}
		
		int GetSize(){
			return size_;
		}
};

int opp(char ch){
	if('#' == ch)
		return 0;
	else if('+' == ch || '-' == ch)
		return 1;
	else if('*' == ch || '/' == ch)
		return 2;
}

int main(){
	string str;
	LinkStack<int> s_num;
	LinkStack<char> s_opp;
	cin >> str;
	str.push_back('#');
	for(int i = 0;i < str.length();i++){
		if(str[i] >= '0' && str[i] <= '9')
			continue;
		if(str[i] < '0' || str[i] > '9'){
			int cnt = 0, k = 1;
			for(int j = i - 1;j >= 0 && ('0' <= str[j] && str[j] <= '9');j--){
				cnt += (str[j] - '0') * k;
				k *= 10;
			}
			s_num.Push(cnt);
		}
		if(s_opp.Empty() || opp(str[i]) > opp(s_opp.Top()))
			s_opp.Push(str[i]);
		else{
			while(!s_opp.Empty() && opp(str[i]) <= opp(s_opp.Top())){
				char ch = s_opp.Top();
				s_opp.Pop();
				int num1 = s_num.Top();s_num.Pop();
				int num2 = s_num.Top();s_num.Pop();
				int res = 0;
				if('+' == ch)
					res = num2 + num1;
				else if('-' == ch)
					res = num2 - num1;
				else if('*' == ch)
					res = num2 * num1;
				else if('/' == ch)
					res = num2 / num1;
				s_num.Push(res);
			}
			s_opp.Push(str[i]);
		}
	}
	cout << s_num.Top();
	return 0;
}