用栈实现表达式计算_文档下载
亿万文档 免费下载
当前位置： &
& 用栈实现表达式计算
用栈实现表达式计算
两种方法利用栈对表达式进行计算
一、设计思想
利用栈将中缀表达式转化成后缀表达式再进行计算。
（1）构造char类型的栈函数以及栈的相关函数（出栈函数、进栈函数、创建栈函数、销毁栈函数、判断栈是否为空函数、看栈顶函数等）。
（2）在main函数中让用户进行输入，将用户输入的字符串进行循环、判断（如果数字字符后面的是运算符，则在数字字符后加“#”以便进行区分；否则，继续循环。）并将判断后的字符串传递到新的数组中，循环结束后，再将数组传递给中缀表达式转后缀表达式函数（Min_Back()）。
（3）中缀表达式转后缀表达式函数是利用运算符的优先级进行判断来将中缀表达式转换成后缀表达式的函数。函数中利用构建的栈以及栈的相关函数对运算符进行操作：先看栈顶，如果栈为空或栈顶元素为‘（’或者栈顶元素为‘+’或‘―’并且现有运算符为‘*’、‘/’或‘%’又或是现有运算符为‘（’，则现有元素进栈；否则，再对现有元素进行判断：如果现有元素为‘）’，运算符出栈直到‘（’出栈；否则，运算符出栈直到栈空或者栈顶元素的优先级低于现有运算符，现有运算符才进栈。循环结束后，将栈中的运算符全部依次输出，最后将后缀表达式传递给求值函数（countfor()），再销毁栈。 （4）求值函数中首先是利用strtod()函数将数字字符串转换成double类型的数字，然后构建一个数字栈，将转换后的数字传递到栈中，每当遇到运算符时，就从数字栈中“扔出”两个数字进行相应的运算，循环结束后，将数字栈中的数字“扔出”，并输出成为表达式最终的结果。
利用创建的两个栈直接对表达式进行计算。
（1）分别构建一个char类型和一个double类型的栈函数以及栈的相关函数（出栈函数、进栈函数、创建栈函数、销毁栈函数、判断栈是否为空函数、看栈顶函数等）。
（2）在main函数中让用户进行输入，将用户输入的字符串进行循环、判断（如果数字字符后面的是运算符，则在数字字符后加“#”以便进行区分；否则，继续循环。）并将判断后的字符串传递到新的数组中，循环结束后，再将数组传递给中缀表达式转后缀表达式函数（Countfor ()）。
（3）在Countfor()函数中先创建一个数字栈和一个符号栈，对表达式进行循环，直到元素为’\0’。在循环中如果元素为数字、点或者#，将元素赋给新的数组Consist[]，再判断下一个元素是否为#，若是则利用strtod()函数将数组中的字符串转换成double类型的数字，然后数字进栈，清空数组Consist[]；否则，继续判断。若元素不为数字、点或者#，则先看栈顶，如果栈为空或栈顶元素为‘（’或者栈顶元素为‘+’或‘―’并且现有元素为‘*’、‘/’或‘%’又或是现有元素为‘（’，则现有元素进栈；否则，再对现有元素进行判断：如果现有元素为‘）’，运算符出栈直到‘（’出栈；否则，运算符出栈直到栈空或者栈顶元素的优先级低于现有运算符，现有运算符才进栈。每当有一个运算符出栈，就从数栈中取两个数与运算符一起传递给Judge()函数,并将函数的返回值压入栈中。循环结束后，将栈中的运算符全部依次输出，每当有一个运算符出栈，就从数栈中取两个数与运算符一起传递给Judge()函数,并将函数的返回值压入栈中，最后输出数字栈中的数字成为表达式的最终结果，再
Word文档免费下载： （下载1-23页，共23页）
用堆栈实现表达式计算用堆栈实现表达式计算隐藏&& 用堆栈实现表达式计算 ---...*/ l_pop(&operand2,&numtop); /* ...运算分量2出栈... */ l_pop(&opera...c语言 栈 用两种方式实现表达式计算_计算机软件及应用_IT/计算机_专业资料。本项目用两种方式实现表达式自动计算:一是,用扫两遍表达式的方法;二是,用扫一遍表达式的...用栈实现的表达式计算 隐藏&& #include&stdio.h& #include&stdlib.h& #include&windows.h& #define MAXNUM 10 #define overflow -1 typedef struct node { ...C语言实现表达式计算_IT/计算机_专业资料。数据结构的一个课设论文,采用C语言建立栈,并两种方式实现表达式的计算用两种方式实现表达式自动计算 一、设计思想两种算法首...栈的应用――计算表达式栈的应用――计算表达式隐藏&& 挺久之前写的一个作业,ACM 选修课的,用栈实现的计算表达式,有两种,一种是将表达 式转换为后缀表达式再计...用两种方式实现表达式自动计算 数据结构(双语)――项目文档报告用两种方式实现...所以表达式不可能严格的从左 到右进行,因此我们借助栈和数组来实现表达式的求值...用栈实现表达式计算 23页 7下载券 实验四 数学表达式计算... 5页 2下载券 ...用栈来计算数学表达式#include &stdafx.h...人们将用链式存储结构表示的栈称作“链栈”。 链栈通常用一个无头结点的单链表...利用栈结构实现表达式计算 中缀转化成后缀的算法: ? ? ? ? 设置一个运算栈,...栈-表达式计算理论 隐藏&& 理论: 理论:表达式的表示形式有中缀、前缀和后缀 3 中形式。中缀表达式按操作符 的优先级进行计算(后面代码实现只包括+、-、*、\,小...栈的应用――表达式计算_IT/计算机_专业资料。NOIP栈的应用――表达式计算 栈的应用――表达式计算 ――保定二中 刘中一一、中缀表达式和后缀表达式 后缀表达式的优点...5915人阅读
数据结构（10）
通常人在书写的时候习惯是书写中缀表达式也叫逆波兰式，然而在计算机处理的时候中缀表达式的效率远小于后缀表达式，即操作数在前面，运算符在后面例如：
中缀表达式 A+B & & 后缀表达式AB+
& & & & & & & & &A+B*C & & & & & & & & & & ABC*+
& & & & & & & &A*B+C*D & & & & & & & &AB*CD*+
& & & & & & &D+A/(B_C) & & & & & & &DABC-/+
后缀表达式计算时，所有运算按照运算符出现的顺序，严格从左到右，每个操作符取前两个操作数进行运算，运算后的结果仍然作为下次的操作数，这样做与中缀表达式完全等价，即计算次序和运算结果完全相同，并且不再使用括号，逆波兰式的主要特点在于运算对象(操作数)不变，运算符号反应运算顺序，采用逆波兰式很好的表达简单运算符，其优点在于已与计算机处理表达式，因此算术表达式计算问题进行分解，先将中缀转换为后缀表达式在进行计算。
这个过程一共分为两步，第一步，把输入的表达式转换为后缀表达式，第二步，计算后缀表达式
转化后缀表达式的过程：
1.当读到操作数后存入数组中，
2.当读到运算符的时候，把优先级比这个运算符小或者等于的所有运算符出栈，再把这个运算符入栈
3.当读左括号的时候，入栈
4.当读到右括号得时候，将靠近栈顶的左括号之前的所有运算符出栈，存入数组中然后再将左括号出栈
计算后缀表达式的过程：
对于计算后缀表达式而言，只是按照自然地从左到右的逻辑顺序，当遇到操作数的时候就入栈，当遇到运算符的时候，就取栈顶的前两个元素进行操作，然后操作完的数，再入栈，然后继续扫描，一直直到表达式遍历完，
实现算法如下：
#include&stdio.h&
#include&string.h&
#include&stdlib.h&
#include &string&
#include &stack&
#include&algorithm&
#define MAXN 1000
stack&char&
//定义了一个栈
char *tranfExp(char* exp)
char tempStr[1000];//保存后缀表达式的字符串
int i=0,j=0;
while(exp[i] !='\0')
if(exp[i]&='0' &&exp[i]&='9')
//如果是数字字符串就保存到后缀表达式字符串中
tempStr[j++] = exp[i];
else if(exp[i] == '(' )
//如果是左括号及入栈
s.push(exp[i]);
else if(exp[i] == ')' )
//如果是右括号就把接近栈顶的左括号上面所有的运算符出栈存进字符串中
左括号出栈
while(s.empty() == false)
if(s.top() == '(' )
tempStr[j++] = s.top();
else if(exp[i] == '+' || exp[i] == '-')
//如果的事+-|操作符就把比他优先级高或者等于的所有运算符出栈进入字符串
while(s.empty() == false)
char ch = s.top();
if(ch == '+'||ch == '-'||ch == '/'||ch == '*')
tempStr[j++] = s.top();
s.push(exp[i]);
else if(exp[i] == '*' || exp[i] == '/')
//类似于扫描到+- 只是如果栈中有=-运算符就不用出栈
因为运算符优先级比较小
while(s.empty() == false)
char ch = s.top();
if(ch == '/' || ch=='*')
tempStr[j++] = s.top();
s.push(exp[i]);
while(s.empty() == false)
//把栈中剩余的所有运算符出栈
tempStr[j++] = s.top();
tempStr[j] = 0;
//最后一个赋值为0
也就是字符串结束的标志
return tempS
//返回已经得到的后缀表达式
int calcExp(char* exp)// 计算后缀表达式
puts(exp);
//展示已经得到的后缀
while( !s.empty() )
while(exp[i] != '\0')
if(exp[i]&='0' && exp[i]&='9')
s.push(exp[i]-'0');
else if(exp[i] == '-')
int m = s.top();
int n = s.top();
s.push(n-m);
else if(exp[i] == '+')
int m = s.top();
int n = s.top();
s.push(n+m);
else if(exp[i] == '/')
int m = s.top();
int n = s.top();
s.push(n/m);
else if(exp[i] == '*')
int m = s.top();
int n = s.top();
s.push(n*m);
/* while(s.empty() == false)
printf(&%d&,s.top());
printf(&\n\n\n&);
return s.top();
int main()
char str[1000];
char* tranS
tranStr = (char *)malloc(100*sizeof(char));
printf(&please input expression with kuohao:\n&);
scanf(&%s&,str);
tranfExp(str);//中缀表达式转换为后缀表达式函数
//puts(tranStr); //输出转换后的后缀表达式
printf(&%d&,calcExp(tranStr));
&&相关文章推荐
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：241051次
积分：4803
积分：4803
排名：第5918名
原创：233篇
转载：14篇
评论：22条
(3)(5)(2)(3)(4)(9)(9)(2)(28)(56)(4)(11)(3)(13)(26)(11)(13)(8)(1)(10)(3)(15)(9)浅谈C/C++ 语言中的表达式求值_C 语言
经常可以在一些讨论组里看到下面的提问：“谁知道下面C语句给n赋什么值？”
m = 1; n = m+++m++;
最近有位不相识的朋友发email给我，问为什么在某个C++系统里，下面表达式打印出两个4，而不是4和5：
a = 4; cout && a++ &&
C++ 不是规定 && 操作左结合吗？是C++ 书上写错了，还是这个系统的实现有问题？
注：运行a = 4; cout && a++ &&
如在Visual c++ 6.0中，得到的是4和4；在Visual Studio中，得到的是4和5.
到底哪个是对的呢？请详看后面的分析！
要弄清这些，需要理解的一个问题是：如果程序里某处修改了一个变量（通过赋值、增量/减量操作等），什么时候从该变量能够取到新值？有人可能说，“这算什么问题！我修改了变量，再从这个变量取值，取到的当然是修改后的值！”其实事情并不这么简单。
C/C++ 语言是“基于表达式的语言”，所有（包括赋值）都在表达式里完成。“x = 1;”就是表达式 “x = 1”后加表示语句结束的分号。要弄清程序的意义，首先要理解表达式的意义，也就是：1）表达式所确定的计算过程；2）它对环境（可以把环境看作 当时可用的所有变量）的影响。如果一个表达式（或子表达式）只计算出值而不改变环境，我们就说它是引用透明的，这种表达式早算晚算对其他计算没有影响（不 改变计算的环境。当然，它的值可能受到其他计算的影响）。如果一个表达式不仅算出一个值，还修改了环境，就说这个表达式有副作用（因为它多做了额外的事）。a++ 就是有副作用的表达式。这些说法也适用于其他语言里的类似问题。
现在问题变成：如果C/C++ 程序里的某个表达式（部分）有副作用，这种副作用何时才能实际体现到使用中？为使问题更清楚，我们假定程序里有代码片段 “...a[i]++ ... a[j] ...”，假定当时i与j的值恰好相等（a[i] 和a[j] 正好引用同一数组元素）；假定a[i]++ 确 实在a[j] 之前计算；再假定其间没有其他修改a[i] 的动作。在这些假定下，a[i]++ 对 a[i] 的修改能反映到 a[j] 的求值中吗？ 注意：由于 i 与 j 相等的问题无法静态判定，在目标代码里，这两个数组元素访问（对内存的访问）必然通过两段独立代码完成。现代计算机的计算都在寄 存器里做，问题现在变成：在取 a[j] 值的代码执行之前，a[i] 更新的值是否已经被（从寄存器）保存到内存？如果了解语言在这方面的规定，这个问 题的答案就清楚了。
程序语言通常都规定了执行中变量修改的最晚实现时刻（称为顺序点、序点或执行点）。程序执行中存在一系列顺序点
（时 刻），语言保证一旦执行到达一个顺序点，在此之前发生的所有修改（副作用）都必须实现（必须反应到随后对同一存储位置的访问中），在此之后的所有修改都还 没有发生。在顺序点之间则没有任何保证。对C/C++ 语言这类允许表达式有副作用的语言，顺序点的概念特别重要。
现在上面问题的回答已经很清楚了：如果在a[i]++ 和a[j] 之间存在一个顺序点，那么就能保证a[j] 将取得修改之后的值；否则就不能保证。
C/C++语言定义（语言的参考手册）明确定义了顺序点的概念。顺序点位于：
1. 每个完整表达式结束时。完整表达式包括变量初始化表达式，表达式语句，return语句的表达式，以及条件、循环和switch语句的控制表达式（for头部有三个控制表达式）；
2. 运算符 &&、||、?: 和逗号运算符的第一个运算对象计算之后；
3. 函数调用中对所有实际参数和函数名表达式（需要调用的函数也可能通过表达式描述）的求值完成之后（进入函数体之前）。
假设时刻ti和ti+1是前后相继的两个顺序点，到了ti+1，任何C/C++ 系统（VC、BC等都是C/C++系统）都必须实现ti之后发生的所有副 作用。当然它们也可以不等到时刻ti+1，完全可以选择在时段 [t, ti+1] 之间的任何时刻实现在此期间出现的副作用，因为C/C++ 语言允许 这些选择。
前面讨论中假定了a[i]++ 在a[i] 之前做。在一个程序片段里a[i]++ 究竟是否先做，还与它所在的表达式确定的计算过程有关。我们都熟悉C/C++ 语言有关优先级、结合性和括号的规定，而出现多个运算对象时的计算顺序却常常被人们忽略。看下面例子：
(a + b) * (c + d) fun(a++, b, a+5)
这里“*”的两个运算对象中哪个先算？fun及其三个参数按什么顺序计算？对第一个表达式，采用任何计算顺序都没关系，因为其中的子表达式都是引用透明的。 第二个例子里的实参表达式出现了副作用，计算顺序就非常重要了。少数语言明确规定了运算对象的计算顺序（Java规定从左到右），C/C++ 则有意不予 规定，既没有规定大多数二元运算的两个对象的计算顺序（除了&&、|| 和 ，），也没有规定函数参数和被调函数的计算顺序。在计算第二 个表达式时，首先按照某种顺序算fun、a++、b和a+5，之后是顺序点，而后进入函数执行。
不少书籍在这些问题上有错（包括一些很流行的书）。例如说C/C++ 先算左边（或右边），或者说某个C/C++ 系统先计算某一边。这些说法都是错误 的！一个C/C++ 系统可以永远先算左边或永远先算右边，也可以有时先算左边有时先算右边，或在同一表达式里有时先算左边有时先算右边。不同系统可能采 用不同的顺序（因为都符合语言标准）；同一系统的不同版本完全可以采用不同方式；同一版本在不同优化方式下，在不同位置都可能采用不同顺序。因为这些做法 都符合语言规范。在这里还要注意顺序点的问题：即使某一边的表达式先算了，其副作用也可能没有反映到内存，因此对另一边的计算没有影响。
回到前面的例子：“谁知道下面C语句给n赋什么值？”
m = 1; n = m++ +m++;
正确回答是：不知道！语言没有规定它应该算出什么，结果完全依赖具体系统在具体上下文中的具体处理。其中牵涉到运算对象的求值顺序和变量修改的实现时刻问题。对于：
cout && a++ &&
我们知道它是
(cout.operator &&(a++)).operator && (a);
的简写。先看外层函数调用，这里需要算出所用函数，还需要计算a的值。语言没有规定哪个先算。如果真的先算函数，这一计算中出现了另一次函数调用，在被调 函数体执行前有一个顺序点，那时a++的副作用就会实现。如果是先算参数，求出a的值
4，而后计算函数时的副作用当然不会改变它（这种情况下输出两个 4）。当然，这些只是假设，实际应该说的是：这种东西根本不该写，讨论其效果没有意义。
有人可能说，为什么人们设计 C/C++时不把顺序规定清楚，免去这些麻烦？C/C++ 语言的做法完全是有意而为，其目的就是允
许编译器采用任何求值顺序，使编译器在优化中可以根据需要调整实现表达式求值的指令序列，以得到效率更高的代码。
像 Java那样严格规定表达式的求值顺序和效果，不仅限制了语言的实现方式，还要求更频繁的内存访问（以实现副作用），这些可能带来可观的效率损失。应该 说，在这个问题上，C/C++和Java的选择都贯彻了它们各自的设计原则，各有所获（C/C++ 潜在的效率，Java更清晰的程序行为），当然也都有 所失。还应该指出，大部分程序设计语言实际上都采用了类似C/C++的规定。
讨论了这么多，应该得到什么结论呢？C/C++ 语言的规定告诉我们，任何依赖于特定计算顺序、依赖于在顺序点之间实现修改效果的表达式，其结果都没有保证。程序设计中应该贯彻的规则是：如果在任何“完整表达式”（形成一段由顺序点结束的计算）里存在对同一“变量”的多个引用，那么表达式里就不应该出现对这一“变量”的副作用。否则就不能保证得到预期结果。注意：这里的问题不是在某个系统里试一试的问题，因为我们不可能试验所有可能的表达式组合形式以及所有可能的上下文。这里讨论的是语言，而不是某个实现。总而言之，绝不要写这种表达式，否则我们或早或晚会某种环境中遇到麻烦。
后记：去年参加一个学术会议，看到有同行写讨论某个C系统里表达式究竟按什么顺序求值，并总结出一些“规律”。从讨论中了解到某“程序员水平考试”出 了这类题目。这使我感到很不安。今年给一个教师学习班讲课，发现许多专业课教师也对这一基本问题也不甚明了，更觉得问题确实严重。因此整理出这篇短文供大 家参考。
以上这篇浅谈C/C++ 语言中的表达式求值就是小编分享给大家的全部内容了，希望能给大家一个参考，也希望大家多多支持云栖社区。在C++中使用栈来把中缀表达式转换为后缀表达式并求值，简单明了 - qq_的博客 - CSDN博客
在C++中使用栈来把中缀表达式转换为后缀表达式并求值，简单明了
& & & & & & & &&
#include&iostream&
#include&stdlib.h&//头文件包含atoi()函数
using namespace std;
typedef char T;
class stack{
T data[<span style="color:#0];
stack() :sz(){}
void push(const T& d){
if (full()) throw &满&;
data[sz&#43;&#43;] = d;
void pop(){
if (empty()) throw &空&;
if (empty()) throw&空&;
return data[sz - <span style="color:#];
T undertop(){
if (empty()) throw&空&;
return data[sz-<span style="color:#];
int Ssz(){//返回栈的元素数量
return sz;
char Sdata(const int i){//返回栈相应位置的元素，栈低为位置0
return data[i];
bool empty(){ return sz == <span style="color:#; }
bool full(){ return sz == <span style="color:#0; }
//c1高于c2返回true,否则返回false
bool prior(char c1, char c2){
return (c1 == '*' || c1 == '/') && (c2 == '&#43;' || c2 == '-');
int main()
string str = &1&#43;4&;
stack //结果栈
stack //运算栈
stack //计算结果栈
stack //计算运算栈
for (int i = <span style="color:#; i&str.length(); i&#43;&#43;){
ch = str[i];
if (ch &= '0'&&ch &= '9'){//是数字的话就把ch放入res结果栈中
res.push(ch);
else if ('(' == ch){
exp.push(ch);
else if (')' == ch){
while (exp.top() != '('){
res.push(exp.top());
exp.pop();
exp.pop();
else{//是运算符
while (!exp.empty() && exp.top() != '('//当exp运算栈不为空且栈顶元素不为'('且ch优先级低于或等于栈顶元素
&&!prior(ch, exp.top())){
res.push(exp.top());
exp.pop();
exp.push(ch);
while (!exp.empty()){
res.push(exp.top());
exp.pop();
while (!res.empty()){
cout && res.top();
res.pop();
cout&&&-----------------&&&
for(int i=<span style="color:#;i&cres.Ssz();i&#43;&#43;){
if(cres.Sdata(i)&='0'&&cres.Sdata(i)&='9'){//如果是数字就放入数字栈
num.push(cres.Sdata(i));
else if(cres.Sdata(i)=='*'){//如果符号是乘号
// a=atoi(num.top())*atoi(num.undertop());//atoi()把字符串转化为整形数
int a=(num.undertop()-<span style="color:#/*或者0*/)*(num.top()-<span style="color:#/*或者0*/);//字符减去48就转化成int型
char c=a&#43;'0';
//int型加上'0'就转化为char型
num.pop();
num.pop();
num.push(c);
else if(cres.Sdata(i)=='/'){
int a=(num.undertop()-<span style="color:#)/(num.top()-<span style="color:#/*或者0*/);
char c=a&#43;'0';
num.pop();
num.pop();
num.push(c);
else if(cres.Sdata(i)=='&#43;'){
int a=(num.undertop()-<span style="color:#/*或者0*/)&#43;(num.top()-<span style="color:#/*或者0*/);
c=a&#43;'0';
num.pop();
num.pop();
num.push(c);
else if(cres.Sdata(i)=='-'){
int a=(num.undertop()-<span style="color:#/*或者0*/)-(num.top()-<span style="color:#/*或者0*/);
c=a&#43;'0';
num.pop();
num.pop();
num.push(c);
cout&&num.top()&&
我的热门文章
即使是一小步也想与你分享}