本文共 3810 字，大约阅读时间需要 12 分钟。

昨天学习了数据结构栈，并实现了栈的顺序存储结构和链式存储结构。今天就实现“大话数据结构”中对栈的应用举例。原理省略，书比我讲得好，直接上代码吧。

应用1：斐波那契数列实现 输出斐波那契数列前10个元素，比较简单就不再赘述。

#include
   
    using namespace std;int Fbl(int i){
   	if (i < 2)		return i == 0 ? 0 : 1;	return Fbl(i - 2) + Fbl(i - 1);}void main(){
   	for (int i = 0; i < 10; i++)		cout << i << "# " << Fbl(i) << endl;}
   

应用2：四则运算表达式求值

问题描述： 平时我们使用的形如“9 + (3-1) * 3 + 10 / 2”的表达式叫做中缀表达式。使用栈实现四则运算时，就需要将中缀表达式改写成后缀表达式“9 3 1 - 3 * + 10 2 / +”。因此这个实现主要涉及两个部分： 1、中缀表达式如何转换为后缀表达式； 2、后缀表达式如何求值； 由于书中所述已经很明白了，因此就省略。 实现想法： 输入一个string对象，包含有四则运算符号和数字以及小括号。新建类私有成员为转换前字符串和转换后字符串以及计算结果。目前该实例只支持使用整型数字，计算结果也都舍弃了小数部分。类的共有成员包括一些基本操作函数。 需要注意的问题： 主要是数字位数不确定，中缀表达式转后缀表达式，以及后缀表达式计算结果的过程中都需要注意如何编码及解码数字。 函数说明：

class Expression{
   private:	string data;   //存储转换前表达式（中缀表达式）	string trans_data;   //存储转换后表达式（后缀表达式）	int result;   //输出计算结果public:	Expression() {
   };   //默认构造函数	Expression(string &s) {
    data = s; }   //自定义构造函数	void Transfer();   //中缀表达式转后缀表达式	void ResetData(string &s);   //重新为data成员赋值	void Calculate();    //计算结果	int Result() {
    return result; }   //返回计算的结果	string & Trans_result() {
    return trans_data; }   //返回转换的表达式};

演示实例：

Enter a arithmetic expression:3+(9*(5-2)/2-1)After transform:3  9  5 2 - *2 /1 -+Calculate result is:15

头文件：

#pragma once#ifndef EXPRESSION_H_#define EXPRESSION_H_#include
   
    #include
    
     #include
     
      using namespace std;class Expression{
   private:	string data;	string trans_data;	int result;public:	Expression() {
   };	Expression(string &s) {
    data = s; }	void Transfer();	void ResetData(string &s);	void Calculate();	int Result() {
    return result; }	string & Trans_result() {
    return trans_data; }};void Expression::ResetData(string &s){
   	data = s;}void Expression::Transfer(){
   	stack
      
        temp;	for (int i = 0; i < data.size(); i++) {
   		while (isalnum(data[i])) {
   			trans_data += data[i];			i++;		}		trans_data += ' ';		if (data[i] == '(')			temp.push('(');		else if (data[i] == ')') {
   			while (temp.top() != '(') {
   				trans_data += temp.top();				temp.pop();			}			temp.pop();		}		else {
   			while (!temp.empty() && (temp.top() == '*' || temp.top() == '/')) {
   				trans_data += temp.top();				temp.pop();			}			while (!temp.empty() && (temp.top() == '+' || temp.top() == '-') &&				(data[i] == '+' || data[i] == '-'))			{
   				trans_data += temp.top();				temp.pop();			}			temp.push(data[i]);		}	}	while (!temp.empty()) {
   		trans_data += temp.top();		temp.pop();	}}void Expression::Calculate(){
   	stack
       
         temp;	for (int i = 0; i < trans_data.size(); i++) {
   		//cout << i << ": " << trans_data[i] << endl;		if (trans_data[i] == ' ')			continue;		else if (isalnum(trans_data[i])) {
   			int num = 0;			while (isalnum(trans_data[i])) {
   				num = num * 10 + (trans_data[i]-'0');				i++;			}			i--;			temp.push(num);		}		else {
   			int a, b;			switch (trans_data[i])			{
   			case '+':				a = temp.top();				temp.pop();				b = a + temp.top();				temp.pop();				temp.push(b);				break;			case '-':				a = temp.top();				temp.pop();				b = temp.top() - a;				temp.pop();				temp.push(b);				break;			case'*':				a = temp.top();				temp.pop();				b = temp.top() * a;				temp.pop();				temp.push(b);				break;			case '/':				a = temp.top();				temp.pop();				b = temp.top() / a;				temp.pop();				temp.push(b);				break;			default:				break;			}		}			}	result = temp.top();}#endif // !EXPRESSION
       
      
     
    
   

主程序：

#include
   
    #include"expression.h"using namespace std;void main(){
   	Expression test;	cout << "Enter a arithmetic expression: \n";	string input;	getline(cin, input);	test.ResetData(input);	test.Transfer();	cout << "After transform: \n";	cout << test.Trans_result() << endl;	cout << "Calculate result is: \n";	test.Calculate();	cout << test.Result() << endl;}
   

转载地址：http://rsyci.baihongyu.com/