数据结构实验：栈实现计算器(表达式计算）

本文主要是介绍数据结构实验：栈实现计算器(表达式计算），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

原创作品转载请注明出处http://blog.csdn.net/acvcla/article/details/41732447

欢迎抄袭，造福各位伸手党

/*************************************************************************> 转载请注明出处http://blog.csdn.net/acvcla/article/details/41732447> File Name: evaluator.cpp> Author: acvcla> version 1.01> QQ:acvcla@gmail.com > Mail: acvcla@gmail.> Created Time: 2014年11月17日 星期一 23时34分13秒>本计算器支持加减乘除四种运算,支持浮点,输入表达式后,按回车计算结果>退出请输入EOF(win下按ctrl+z,linux下按ctrl+d)>代码在G++环境下编译通过,推荐使用codeblocks编译运行,强烈不推荐VC++6.0>若没有codeblocks,可以使用dev c++或者VS2010以上版本
*************************************************************************/
#include<iostream>
#include<string>
#include<cctype>
using namespace std;
const int init_size=10;
const int maxn=100005;
#define Debug
template <typename T>
struct Stack
{string name;T *base,*top;int size;Stack(const string s="None"):name(s)/*初始化栈*/{top=base=new T[size=init_size];}void Expansion();void push(T e)/*入栈*/{Expansion();#ifdef Debugcout<<name<<"    push		"<<e<<endl;#endif*top++=e;}T & Top()const/*取栈顶引用*/{return *(top-1);}bool empty()const/*判断栈是否为空*/{return base==top;}T pop()/*返回栈顶元素并出栈*/{if(empty()) {cout<<name<<" is empty"<<endl;return T(NULL);}#ifdef Debugcout<<name<<"    pop		"<<*(top-1)<<endl;#endifreturn *(--top);}
};template<typename T>
void Stack<T>::Expansion()/*扩容函数*/
{if(top-base>=size) {T *newbase= new T[size<<=1];/*成倍增加减少均摊复杂度,均摊O(1)*/int i=0;while(base+i!=top)*(newbase+i)=*(base+i);/*复制到新开辟的空间*/delete base;/*释放旧的空间*/base=newbase;}
}
void readnum(char *&S,Stack<double>&f)/*从S中读取数字并将S指向数字后的第一个操作符*/
{double tmp=0,c=1;int found=0;while(isdigit(*S)||*S=='.') {if(*S=='.'){found=1;S++;continue;}if(found)c*=10;tmp=tmp*10+(*S)-'0';S++;}f.push(tmp/c);
}
double calcu(double a,char op,double b)/*计算a op b*/
{switch(op){case '+':return a+b;case '-':return a-b;case '*':return a*b;case '/':return a/b;}
}
int optoi(const char op)/*将操作符转成数字*/
{switch(op) {case '+':return 0;case '-':return 1;case '*':return 2;case '/':return 3;case '(':return 4;case ')':return 5;case '\0':return 6;}
}
char oderbetween(const char a,const char b)/*判断操作符优先级*/
{const int op_kind=10;const char pri[op_kind][op_kind]={">><<<>>",">><<<>>",">>>><>>",">>>><>>","<<<<<= ","       ","<<<<< ="};return pri[optoi(a)][optoi(b)];
}
double evaluate(char *S)/*算法主过程*/
{Stack<double>opnd("opnd");/*操作数栈*/Stack<char>optr("optr");/*操作符栈*/optr.push('\0');while(!optr.empty()){if(isdigit(*S)||*S=='.')readnum(S,opnd);/*读取数字*/else{if(*S==' ') {S++;continue;}switch(oderbetween(optr.Top(),*S)) {/*根据优先级进行计算*/case '<':optr.push(*S);S++;break;case '=':optr.pop();S++;break;case '>': {char op=optr.pop();double opnd2=opnd.pop(),opnd1=opnd.pop();opnd.push(calcu(opnd1,op,opnd2));break;}}}}return opnd.pop();
}
char exptr[maxn];/*表达式数组*/
int main(int argc, char const *argv[])
{while(cin>>exptr) {cout<<evaluate(exptr)<<endl;}return 0;
}

这篇关于数据结构实验：栈实现计算器(表达式计算）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---