/********************************************************************************/
/* 计算器程序 */
/* */
/* 2010-3-8 */
/* */
/* 说明: Calculator类,用于通过给定四则运算表达式, 求出表达式的代数值 */
/* */
/* 示例: #include <iostream> */
/* #include <string> */
/* #include "Calculator.h" */
/* void main() */
/* { */
/* string expression="2.3+(25-0.6*3.2^1.6)/(5-1.5^2)"; */
/* Calculator c(expression); */
/* cout<<c.Run()<<endl; */
/* getchar(); */
/* } */
/* */
/* 输出:9.98791 */
/* */
/********************************************************************************/
//节点类, 用于保存浮点数[flag=0],或者运算符[flag=1]
#pragma region
class Item
{
public:
Item(){} //构造函数
Item(string _value,int _flag) //重载构造函数
{
value=_value; flag=_flag;
}
string value; //保存浮点数,或者运算符
int flag; //标志位
Item& operator=(Item& item) //运算符重载
{
value=item.value;
flag=item.flag;
return *this;
}
};
#pragma endregion
/*===================================================================================*/
/* */
/* 各个算术操作符的优先级 */
/* ------------------------------------------------------------------------------ */
/* | 操作符 | # | ( | ^ | * / % | + - | ) | */
/* ------------------------------------------------------------------------------ */
/* | isp | 0 | 1 | 7 | 5 | 3 | 8 | */
/* ------------------------------------------------------------------------------ */
/* | icp | 0 | 8 | 6 | 4 | 2 | 1 | */
/* ------------------------------------------------------------------------------ */
/* */
/*===================================================================================*/
#pragma region
int isp(string s)
{
if(s=="#")
return 0;
if(s=="(")
return 1;
if(s=="^")
return 7;
if(s=="*"||s=="/"||s=="%")
return 5;
if(s=="+"||s=="-")
return 3;
if(s==")")
return 8;
return -1;
}
int icp(string s)
{
if(s=="#")
return 0;
if(s=="(")
return 8;
if(s=="^")
return 6;
if(s=="*"||s=="/"||s=="%")
return 4;
if(s=="+"||s=="-")
return 2;
if(s==")")
return 1;
return -1;
}
#pragma endregion
#pragma region
class Calculator
{
public:
string expression; //要计算的表达式
DCirList<Item> inlist; //存储中缀表达式的链表
DCirList<Item> postlist; //存储后缀表达式的链表
LinkStack<Item> stack; //存储符号的栈
LinkStack<float> result; //存储结果
Calculator(string _expression); //构造函数
void GetInfix(); //取得中缀表达式
void GetPostfix(); //取得后缀表达式
float Run(); //求结果
};
#pragma endregion
#pragma region
Calculator::Calculator(string _expression)
{
expression=_expression;
expression.append(1,'#');
}
/*====================================================================================*/
/* 字符串转中缀表达式算法: */
/* */
/* 一.从字符串第一个字符开始扫描,遇到数字或小数点,累加该字符到value中,直到遇到运算符. */
/* 将value, 以及此运算符存入到中缀表达式链表. */
/* 二.如果字符串的最后一位为数字, 则扫描完后,直接将value存入到中缀表达式链表. */
/* */
/*====================================================================================*/
void Calculator::GetInfix()
{
string value=""; int flag=0; Item node1,node2;
for(int i=0;i<expression.length();i++)
{
if( (int)expression[i]==46||((int)expression[i]>=48&&(int)expression[i]<=57) )
{
flag=0;
value.append(1,expression[i]);
if(i!=expression.length()-1)
continue;
else
{
node1.value=value; node1.flag=0;
inlist.PushBack(node1);
break;
}
}
if(value!="")
{
node1.value=value; node1.flag=0;
inlist.PushBack(node1);
}
node2.value=expression[i]; node2.flag=1;
inlist.PushBack(node2);
value="";
}
}
/*====================================================================================*/
/* 中缀表达式转化成后缀表达式算法: */
/* */
/* 一.操作符栈初始化,将结束符#进栈,然后读取中缀表达式链表的首个结点元素item. */
/* 二.重复执行以下步骤,直到读到item.value='#', 同时栈顶的操作符也是#, 停止循环. */
/* 1.若item是操作数, 则存入后缀表达式链表,并读取下一个元素. */
/* 2.若item是操作符, 判断item的优先级icp和当前位于栈顶的操作符oper的优先级isp. */
/* 3.(1)若icp(item.value)>isp(oper.value), 令item进栈,并读取下一个元素. */
/* (2)若icp(item.value)<isp(oper.value), 退栈, 并将此元素存入后缀表达式链表. */
/* (3)若icp(item.value)=isp(oper.value), 退栈, 若退出的是'(', 则读取下一个元素. */
/* */
/*====================================================================================*/
void Calculator::GetPostfix()
{
Item item("#",1);
stack.Push(item);
item=inlist.PopFront();
while(!stack.IsEmpty())
{
if(item.flag==0)
{
postlist.PushBack(item);
item=inlist.PopFront();
}
else
{
Item oper=stack.GetTop()->data;
if(isp(oper.value)<icp(item.value))
{
stack.Push(item);
item=inlist.PopFront();
}
else if(isp(oper.value)>icp(item.value))
{
postlist.PushBack(stack.Pop());
}
else
{
if(stack.Pop().value=="(")
item=inlist.PopFront();
}
}
}
}
/*====================================================================================*/
/* 通过后缀表达式计算表达式的值算法: */
/* */
/* 顺序扫描后缀表达式链表的每一项,然后根据它的类型,做如下相应操作: */
/* 1.如果该项是操作数,则将其压入栈中; */
/* 2.如果该项是操作符<op>,则连续从栈中弹出两个操作数Y,X,形成运算指令X<op>Y; */
/* 3.将计算结果重新压入栈中; */
/* 4.当表达式的所有项都扫描或处理完之后,栈顶存放的就是最后的计算结果. */
/*====================================================================================*/
float Calculator::Run()
{
float num1,num2;
while(!postlist.IsEmpty())
{
Item item=postlist.PopFront();
if(item.flag==0)
result.Push(atof(item.value.c_str()));
else
{
if(result.IsEmpty())
Error("取右操作数失败!");
num2=result.Pop();
if(result.IsEmpty())
Error("取左操作数失败!");
num1=result.Pop();
switch(item.value[0])
{
case '+': result.Push(num1+num2); break;
case '-': result.Push(num1-num2); break;
case '*': result.Push(num1*num2); break;
case '/':
{
if(num2==0.0)
{
result.ClearStack();
Error("Divide by 0 !");
}
else
result.Push(num1/num2); break;
}
case '%': result.Push((int)num1%(int)num2); break;
case '^': result.Push(pow(num1,num2)); break;
}
}
}
if(result.IsEmpty())
Error("计算失败!");
return result.Pop();
}
#pragma endregion
分享到:
相关推荐
很多涉及计算器程序的的算法都是以栈的相关操作为基础,通过计算器的设计,有利于在学习中更好的理解栈及其相关的操作。 通过对计算器计算过程演示,看到了到它的一些性能及相关优势。 我们在写程序时,大框架已成的...
可执行程序可以实现数学计算公式的复杂运算。下载压缩包后需要减压文件,在目录下在linux命令行输入要计算的公式的字符串即可求出结果,例如在linux命令行下输入执行命令 :./calculator "1+2*3-(6-3)*2+4-1" 即可求...
9.定义并实现循环队列的数据结构。 10.应用队列完成Johnson问题(n个人围成一圈,每个人都有一个号码,从1..n,从1号报数,报到m号的出列,输出出列的号码顺序)。测试:10个人,报到3的出列。
经过这学期对数据结构的学习, 我们学习了理论知识, 了解了数据结构设计的思想, 这些知识都为我们的下一步学习打下了坚实的基础。通过课程设计,一方面是为了检查 我们一个学期来我们学习的成果,另一方面也是为了...
表达式求值问题在程序设计中经常遇见,通过本课程设计,使学生掌握表达式的不同表示形式及相应的求值方法,加深对栈的基本原理和方法的理解和应用,培养学生运用语言编程及调试的能力,运用数据结构解决简单的实际...
表达式计算是实现程序设计语言的基本问题之一,也是栈的应用的一个典型例子。设计一个程序,演示用算符优先法对算术表达式求值的过程。 【基本要求】 以字符序列的形式从终端输入语法正确的、不含变量的整数表达式。...
本工程可以是在学习数据结构和算法的时候应用栈的理论编写的科学计算器(带源码),可以完成如1.5+2*3+(4*5+6)*7类算式的计算。
编写程序,完成手机计算机器中的简单表达式求值,完成+、-、*、/、% 五种混合运算。(难度分为六级) 基本要求:无括号、整数 中级要求:有括号、整数 高级要求:有括号、多位整数 超级要求:有括号、小数 ...
c语言数据结构栈的四则运算(带括号)的实现,里面有解释
为了能锻炼对数据结构各理论知识的熟练程度,我在独立完成程序的过程中,我不仅更深层次的了解得栈的运用和推广,我还了解了数组在数据结构中可以充当很多的作用。运用栈的思想,在数据用进栈和出栈先后的顺序来完成...
栈的实现 链栈的实现 出栈,入栈,栈空 基于栈实现的判断括号配对程序 基于栈实现的中缀表达式转后缀表达式 基于栈实现的后缀表达式计算器
数据结构3.txt 数组完全单元.txt 数组操作.txt 数组递归退出.txt 数组递归退出2.txt 文件加密.txt 文件复制.txt 文件连接.txt 无向图.txt 时间陷阱.txt 杨辉三角形.txt 栈单元加.txt 栈操作.txt 桃子...
《数据结构》实验参考代码2 实验二:使用栈或队列解决一个应用问题 问题描述 设计一个模拟计算器功能的程序,它读入一个表达式,如果是一个正确的表达式(即它 由操作数、圆括号和+、- 、*、/四种运算符组成),则求...
2、实验思路(详细描述解决问题的整体思路、涉及的算法思想及数据结构等) 第一步,从input.txt文件中读取中缀表达式,并应用运算符栈convertopost把中缀表达式转换为后缀表达式,将输出结果存放在一个temp.txt文件...
2012-06-11 21:09 1,553,768 数据结构算法Visual.C.6.0程序集_源码.rar 2012-06-11 21:42 87,040 时域卷积定理的证明.ppt 2012-06-11 21:10 4,371 更改网关IP.rar 2012-06-11 20:57 1,419 栈的实现.txt 2012-06-11 ...
6.9.2 CLR版本的计算器程序 285 6.10 小结 290 6.11 练习 291 6.12 本章主要内容 292 第7章 自定义数据类型 293 7.1 C++中的结构 293 7.1.1 结构的概念 294 7.1.2 定义结构 294 7.1.3 初始化结构 294 7.1.4...
队列和栈:编写一个程序,实现队列和栈的数据结构,支持添加、删除、查找等操作。 图书馆管理系统:编写一个程序,实现图书馆的图书借阅、归还、查询等功能,涉及到数据库的操作。 生日提醒程序:编写一个程序,...
2024/4/9 15:47:03 以下是一些关于蓝桥杯C++案例题和模拟题...这些题目涵盖了各种算法和数据结构的应用,可以帮助提高编程能力和解决实际问题的能力。如果您需要更多具体的题目或解析,请告诉我,我可以提供更多帮助。
第2部分 数值计算与数据结构篇 实例16 常用的几种排序方法 46 实例17 广度优先搜索及深度优先搜索 53 实例18 实现基本的串操作 59 实例19 计算各点到源点的最短距离 62 实例20 储油问题 65 实例21 中奖...
本书全面介绍了应用C语言进行开发的各种技术和技巧,全书共分12章,内容包括基础知识、指针、数据结构、算法、数学应用、文件操作、库函数应用、图形图像、系统调用、加解密与安全性、游戏、综合应用等。全书共提供...