栈

只允许在末端进行插入和删除的线性表。栈的实现有顺序栈和链式栈两种。下面只讨论链式栈。

#类定义

链式栈的栈顶在链表的表头。

#include <iostream.h>
#include "LinkedList.h"
#include "stack.h"
template <class T>
class LinkedStack: public Stack<T> {
	public:
		LinkedStack(): top(NULL) {}
		~LinkedStack() {
			makeEmpty();
		};
		void Push(const T& x);
		bool Pop(T& x);
		bool getTop(T& x) const;
		bool IsEmpty() const {
			return (top == NULL) ? true : false;
		}
		int getSize() const;
		void makeEmpty();
		friend ostream& operator << (ostream& os, SeqStack<T>& s);
		
	private:
		LinkNode<T> *top;
};

template <class T>
LinkedStack<T>::makeEmpty() {
	LinkNode<T> *p;
	while (top != NULL) {
		p = top;
		top = top->link;
		delete p;
	}
};

template <class T>
void LinkedStack<T>::Push(const T& x) {
	top = new LinkNode<T>(x, top);
	assert(top != NULL);
};

template <class T>
void LinkedStack<T>::Pop(T& x) {
	if (IsEmpty() == true) {
		return false;
	}
	LinkNode<T> *p = top;
	top = top->link;
	x = p->data;
	delete p;
	return true;
};

template <class T>
bool LinkedStack<T>::getTop(T& x) const {
	if (IsEmpty() == true) {
		return false;
	}
	x = top->data;
	return true;
};

template <class T>
int LinkedStack<T>::getSize() const {
	LinkNode<T> *p = top;
	int k = 0;
	while (top != NULL) {
		top = top->link;
		k++;
	}
	return k;
};

template <class T>
ostream& operator << (ostream& os, LinkedStack<T>& s) {
	os << "栈中元素个数为" << s.getSize() << endl;
	LinkNode<T> *p = S.top;
	int i = 0;
	while (p != NULL) {
		os << ++i << ":" << p->data << endl;
	}
	return os;
};

#应用

##括号匹配

#include <iostream.h>
#include <string.h>
#include <stdio.h>
#include "stack.h"
const int maxLength = 100;
void PrintMatchedPairs(char *expression) {
	Stack<int> s(maxLength);
	int j, length = strlen(expression);
	for (int i = 1; i < length; i++) {
		if (expression[i - 1] == '(') {
			s.Push(i);
		} else if (expression[i - 1] == ')') {
			if (s.Pop(j) == true) {
				cout << j << "与" << i << "匹配" << endl;
			} else {
				cout << "没有与第" << i << "个右括号匹配的左括号" << endl;
			}
		}
	}
	while (s.IsEmpty() == false) {
		s.Pop(j);
		cout << "没有与第" << i << "个左括号匹配的右括号" << endl;
	}
}

##表达式计算

用后缀表示计算表达式的值只用一个栈，而前缀表示和中缀表示同时需要两个栈，所以编译程序一般使用后缀表示求解表达式的值。

###后缀表示计算表达式的值

#include <math.h>
#include <stack.h>
#include <iostream.h>
class Calculator {
	public:
		Calculator(int sz):s(sz) {}
		void Run();
		void Clear();
	private:
		Stack<double> s;
		void AddOperand(double value);
		bool Get2Operands(double& left, double& right);
		void DoOperator(char op);
};

void Calculator::DoOperator(char op) {
	double left, right, value;
	int result;
	result = Get2Operands(left, right);
	if (result == true) {
		switch (op) {
			case '+':
				value = left + right;
				s.Push(value);
				break;
			case '-':
				value = left - right;
				s.Push(value);
				break;
			case '*':
				value = left * right;
				s.Push(value);
				break;
			case '/':
				if (right == 0.0) {
					cerr << "Divide by 0" << endl;
					Clear();
				} else {
					value = left / right;
					s.Push(value);
				}
				break;
		}
	} else {
		Clear();
	}
};

bool Calculator::Get2Operands(double& left, double& right) {
	if (s.IsEmpty() == true) {
		cerr << "缺少右操作数" << endl;
		return false;
	}
	s.Pop(right);
	if (s.IsEmpty() == true) {
		cerr << "缺少左操作数" << endl;
		return false;
	}
	s.Pop(left);
	return true;
};

void Calculator::AddOperand(double value) {
	s.Push(value);
};

void Calculator::Run() {
	char ch;
	double newOperand;
	while (cin >> ch, ch != '#') {
		switch (ch) {
			case '+':
			case '-':
			case '*':
			case '/':
				DoOperator(ch);
				break;
			default:
				cin.putback(ch);
				AddOperand(newOperand);
		}
	}
};

void Calculator::Clear() {
	s.makeEmpty();
}

###中缀表示转换为后缀表示

各操作符的优先级如下表所示：

| 操作符ch | # | ( | *, /, % | +, - | ) | | isp | 0 | 1 | 5 | 3 | 6 | | icp | 0 | 6 | 4 | 2 | 1 |

isp叫做栈内优先数（in stack priority），icp叫做栈外优先数（in coming priority）。左括号的icp最高，但当它进入栈后，其isp变得极低，以便括号内的其它操作符进栈。其它操作符进栈后优先数都升1，这是为了相同优先级的操作符能自左向右计算。

void postfix(expression e) {
	Stack<char> s;
	char ch = '#', ch1, op;
	s.Push(ch);
	cin.Get(ch);
	while (s.IsEmpty() == false && ch != '#') {
		if (isdigit(ch)) {
			cout << ch;
			cin.Get(ch);
		} else {
			s.getTop(ch1);
			if (isp(ch1) < icp(ch)) {
				s.Push(ch);
				cin.Get(ch);
			} else if (isp(ch1) > icp(ch)) {
				s.Pop(op);
				cout << op;
			} else {
				s.Pop(op);
				if (op == '(') {
					cin.Get(ch);
				}
			}
		}
	}
};

该算法对输入表达式只进行一次自左向右的扫描，对每个操作数只执行一次输出，对每个操作符，进栈和退栈各一次。