【数据结构】顺序栈 Stack
发布时间:2020-12-15 06:33:13 所属栏目:安全 来源:网络整理
导读:08年9月入学,12年7月毕业,结束了我在软件学院愉快丰富的大学生活。此系列是对四年专业课程学习的回顾,索引参见:http://www.jb51.cc/article/p-srsfcefa-vo.html 顺序栈各种基本运算算法的实现 栈是只能在某一端插入和删除的特殊线性表。它按照后进先出的
08年9月入学,12年7月毕业,结束了我在软件学院愉快丰富的大学生活。此系列是对四年专业课程学习的回顾,索引参见:http://www.52php.cn/article/p-srsfcefa-vo.html
顺序栈各种基本运算算法的实现
栈是只能在某一端插入和删除的特殊线性表。它按照后进先出的原则存储数据,先进入的数据被压入栈底(push),最后的数据在栈顶(top),需要读数据的时候从栈顶开始弹出数据(top)最后一个数据被第一个读出来。
栈中数据用数组储存,通过top(),push(),pop()基本的函数用以实现其功能,此外我还增加了clear()函数用以清除栈中现有的所有元素 【实验说明】
我选择的题目:书中calculator的编写与改进
1.分析栈要实现的功能从而确定栈类的几种基本成员函数——pop(),pop(),top(),clear(),确定栈中以数组实现数据的存储从而确定栈的成员函数——Stack_entry entry[],count(记录栈中数据数量) 2.编写栈的头文件及实现 3.选择书中计算器的程序以验证栈的各种基本运算。分析书中算法思路及对栈的运用,提出可以改进的地方——将计算器功能封装到类中,并增加清空栈的功能。 4.编写计算器类的头文件及类的实现 5.主函数中通过简单的创建MyClaculator验证程序,并试验各种基本功能。 【相关代码】Stack.h#ifndef STACK_H #define STACK_H enum Error_code{success,underflow,overflow}; const int stackmax=10; typedef double Stack_entry; class Stack{ public: Stack(); bool empty() const; Error_code pop(); Error_code push(const Stack_entry &item); Error_code top(Stack_entry &item) ; Error_code clear(); private: Stack_entry entry[stackmax]; int count; }; #endifStack.cpp #include"stack.h" //implemention //Stack() Stack::Stack(){ count=0; } //pop() Error_code Stack::pop(){ Error_code outcome=success; if(count==0) outcome=underflow; else count--; return outcome; } //push() Error_code Stack::push(const Stack_entry &item){ Error_code outcome=success; if(count>=stackmax) outcome=overflow; else entry[count++]=item; return outcome; } //top() Error_code Stack::top(Stack_entry &item){ Error_code outcome=success; if(count==0) outcome=underflow; else item=entry[count-1]; return outcome; } //clear() Error_code Stack::clear(){ count=0; return success; } //empty() bool Stack::empty() const{ bool outcome=true; if(count!=0) outcome=false; return outcome; }caculator.h #ifndef CALCULATOR_H #define CALCULATOR_H #include"stack.h" class Calculator{ public: //constructor Calculator(); //public function to get command void get_command(); //pubblic funtion to do the command bool do_command(); protected: //As these functions will not be visible to the client //but should be derived classes to access so I declare it as protected functions void PutInNum(); void Add(); void Sub(); void Mul(); void Div(); void ShowResult(); void Clear(); void Quit(); private: //data members char command; Stack numbers; }; #endifcaculator.cpp #include "calculator.h" #include <iostream> using namespace std; //construction Calculator::Calculator(){ command=' '; } //get_command void Calculator::get_command(){ bool waiting =true; cout<<"Select command and press <Enter>:"; while(waiting){ cin>>command; command=tolower(command); if(command=='?'||command=='='||command=='+'|| command=='-'||command=='*'||command=='/'|| command=='q'||command=='c') waiting=false; else cout<<"Please enter a valid command:"<<endl <<"[?]push to stack [=]print top "<<endl <<"[+][-][*][/] are arithmetic operations"<<endl <<"[c]clean the stack"<<endl <<"[Q] quit"<<endl; } } //do_command bool Calculator::do_command(){ get_command(); switch(command){ case '?': PutInNum(); break; case '+': Add(); break; case '-': Sub(); break; case '*': Mul(); break; case '/': Div(); break; case 'c': Clear(); break; case '=': ShowResult(); break; case 'q': return false; } return true; } //Once enter '?': put the next number into stack void Calculator::PutInNum(){ Stack_entry p; cout<<"Enter a real number: "<<flush; cin>>p; if(numbers.push(p)==overflow) cout<<"Warning:Stack full,lost number"<<endl; } //Once enter '+' : Add the numbers in the stack void Calculator::Add(){ Stack_entry p,q; if(numbers.top(p)==underflow) cout<<"Stack empty"<<endl; else{ numbers.top(p); numbers.pop(); if(numbers.top(q)==underflow){ cout<<"Stack has just one entry"<<endl; numbers.push(p); } else{ numbers.pop(); if(numbers.push(p+q)==overflow) cout<<"Warning:Stack full,lost result"<<endl; } } } //Once enter '-': Subtract the numbers in the stack void Calculator::Sub(){ Stack_entry p,q; if(numbers.top(p)==underflow) cout<<"Stack empty"<<endl; else{ numbers.top(p); numbers.pop(); if(numbers.top(q)==underflow){ cout<<"Stack has just one entry"<<endl; numbers.push(p); } else{ numbers.pop(); if(numbers.push(q-p)==overflow) cout<<"Warning:Stack full,lost result"<<endl; } } } //Once enter'*': Multiply the numbers in the stack void Calculator::Mul(){ Stack_entry p,q; if(numbers.top(p)==underflow) cout<<"Stack empty"<<endl; else{ numbers.top(p); numbers.pop(); if(numbers.top(q)==underflow){ cout<<"Stack has just one entry"<<endl; numbers.push(p); } else{ numbers.pop(); if(numbers.push(p*q)==overflow) cout<<"Warning:Stack full,lost result"<<endl; } } } //Once enter '/': Divide the numbers in the stack void Calculator::Div(){ Stack_entry p,q; if(numbers.top(p)==underflow) cout<<"Stack empty"<<endl; else{ numbers.top(p); numbers.pop(); if(p==0){ cout<<"Bed command! The second number is 0 and cannot finishi divide command!"<<endl; } else if(numbers.top(q)==underflow){ cout<<"Stack has just one entry"<<endl; numbers.push(p); } else{ numbers.pop(); if(numbers.push(q/p)==overflow) cout<<"Warning:Stack full,lost result"<<endl; } } } //Once enter '=':Show the result of least command void Calculator::ShowResult(){ Stack_entry p; if(numbers.top(p)==underflow) cout<<"Stack empty"<<endl; else cout<<p<<endl; } //Once enter 'q':Stop the calculation void Calculator::Quit(){ cout<<"Calculation finished!"<<endl; } //Once enter 'c':Clear the stack void Calculator::Clear(){ numbers.clear(); } |