数据结构课程设计-用栈实现表达式求值的方法详解
字体：[ ] 类型：转载 时间：
本篇文章是对在c语言中用栈实现表达式求值的方法进行了详细的分析介绍，需要的朋友参考下
1、需求分析设计一个程序，演示用算符优先法对算术表达式求值的过程。利用算符优先关系，实现对算术四则混合运算表达式的求值。（1）输入的形式：表达式，例如2*(3+4)&&&& 包含的运算符只能有'+' 、'-' 、'*' 、'/' 、'('、 ')'；（2）输出的形式：运算结果，例如2*(3+4)=14；（3）程序所能达到的功能：对表达式求值并输出 2、系统设计1、栈的抽象数据类型定义：ADT Stack{数据对象：D={ai|ai∈ElemSet,i=1,2,…,n,n≥0}数据关系：R1={&ai-1,ai&|ai-1,ai∈D,i=2,…,n}&&&&&&&&& 约定an端为栈顶，ai端为栈底基本操作：Push(&S,e)初始条件：栈S已存在操作结果：插入元素e为新的栈顶元素Pop(&S,&e)初始条件：栈S已存在且非空操作结果：删除S的栈顶元素，并用e返回其值}ADT Stack3、各个模块的主要功能：*Push(SC *s,char c)：把字符压栈*Push(SF *s,float f)：把数值压栈*Pop(SC *s)：把字符退栈*Pop(SF *s)：把数值退栈Operate(a,theta,b)：根据theta对a和b进行'+' 、'-' 、'*' 、'/' 、'^'操作In(Test,*TestOp)：若Test为运算符则返回true，否则返回falseReturnOpOrd(op,*TestOp)：若Test为运算符，则返回此运算符在数组中的下标precede(Aop,Bop)：根据运算符优先级表返回Aop与Bop之间的优先级EvaluateExpression(*MyExpression)：用算符优先法对算术表达式求值完整的程序代码如下： 代码如下:#include"stdio.h"#include"stdlib.h" #include"string.h" #include"math.h"#define true 1 #define false 0 #define OPSETSIZE 8 typedef int S unsigned char Prior[8][8] ={ // 运算符优先级表 &// '+' '-' '*' '/' '(' ')' '#' '^' &/*'+'*/'&','&','&','&','&','&','&','&', &/*'-'*/'&','&','&','&','&','&','&','&', &/*'*'*/'&','&','&','&','&','&','&','&', &/*'/'*/'&','&','&','&','&','&','&','&', &/*'('*/'&','&','&','&','&','=',' ','&', &/*')'*/'&','&','&','&',' ','&','&','&', &/*'#'*/'&','&','&','&','&',' ','=','&', &/*'^'*/'&','&','&','&','&','&','&','&' }; typedef struct StackChar{& &struct StackChar * }SC;&&&&&& //StackChar类型的结点SCtypedef struct StackFloat{& &struct StackFloat * }SF;&&&&&& //StackFloat类型的结点SFSC *Push(SC *s,char c)&&&&&&&&& //SC类型的指针Push，返回p{&SC *p=(SC*)malloc(sizeof(SC)); &p-&c=c; &p-&next=s; & } SF *Push(SF *s,float f)&&&&&&& //SF类型的指针Push，返回p{&SF *p=(SF*)malloc(sizeof(SF)); &p-&f=f; &p-&next=s; & } SC *Pop(SC *s)&&& //SC类型的指针Pop{&SC *q=s; &s=s-& &free(q); & } SF *Pop(SF *s)&&&&& //SF类型的指针Pop{&SF *q=s; &s=s-& &free(q); & } float Operate(float a,unsigned char theta, float b)&&&&& //计算函数Operate{&switch(theta)&{&case '+': return a+b; &case '-': return a-b; &case '*': return a*b; &case '/': return a/b; &case '^': return pow(a,b); &default : return 0; &} } char OPSET[OPSETSIZE]={'+','-','*','/','(',')','#','^'}; Status In(char Test,char *TestOp){&int Find= &for (int i=0; i& OPSETSIZE; i++)&{&&if(Test == TestOp[i])&&&Find= &} &return F } Status ReturnOpOrd(char op,char *TestOp){ &for(int i=0; i& OPSETSIZE; i++)&{&&if (op == TestOp[i])&&&&}}char precede(char Aop, char Bop){ &return Prior[ReturnOpOrd(Aop,OPSET)][ReturnOpOrd(Bop,OPSET)]; } float EvaluateExpression(char* MyExpression){ &// 算术表达式求值的算符优先算法&// 设OPTR和OPND分别为运算符栈和运算数栈，OP为运算符集合 &SC *OPTR=NULL;&&&&&& // 运算符栈，字符元素 &SF *OPND=NULL;&&&&&& // 运算数栈，实数元素 &char TempData[20]; &float Data,a,b; &char theta,*c,Dr[]={'#','\0'}; &OPTR=Push(OPTR,'#'); &c=strcat(MyExpression,Dr); &strcpy(TempData,"\0");//字符串拷贝函数 &while (*c!= '#' || OPTR-&c!='#')&{ &&if (!In(*c, OPSET))&&{ &&&Dr[0]=*c; &&&strcat(TempData,Dr);&&&&&&&&&& //字符串连接函数 &&&c++; &&&if (In(*c, OPSET))&&&{ &&&&Data=atof(TempData);&&&&&& //字符串转换函数(double) &&&&OPND=Push(OPND, Data); &&&&strcpy(TempData,"\0"); &&&} &&} &&else&&& // 不是运算符则进栈 &&{&&&switch (precede(OPTR-&c, *c))&&&{&&&case '&': // 栈顶元素优先级低 &&&&OPTR=Push(OPTR, *c); &&&&c++; &&&& &&&case '=': // 脱括号并接收下一字符 &&&&OPTR=Pop(OPTR); &&&&c++; &&&& &&&case '&': // 退栈并将运算结果入栈 &&&&theta=OPTR-&c;OPTR=Pop(OPTR); &&&&b=OPND-&f;OPND=Pop(OPND); &&&&a=OPND-&f;OPND=Pop(OPND); &&&&OPND=Push(OPND, Operate(a, theta, b)); &&&& &&&} //switch&&} &} //while &return OPND-&f; } //EvaluateExpression int main(void){ &char s[128];&puts("请输入表达式:"); &gets(s);&puts("该表达式的值为:"); &printf("%s\b=%g\n",s,EvaluateExpression(s));&system("pause");&return 0;}测试结果如下：
您可能感兴趣的文章:
大家感兴趣的内容
12345678910
最近更新的内容
常用在线小工具1564人阅读
C、C++（5）
数据结构和算法（7）
表达式求值除了用文法实现之外（文法实现表达式求值看），还可以直接用栈，将中缀表达式转化为后缀表达式。然后再用求表达式的值就轻而易举了。
下面贴程序源码：（可能有点长：）
#include&stack.cpp&
#include&stack.h&
#include&iostream&
该函数有两个功能
1. 输入中缀表达式
2. 将中缀表达式转化为后缀表达式
形参为两个指针分别指向两个数组（一个储存数字，一个储存运算符）
返回值是数字和运算符的总个数（若转化出错，返回-1）
int change(double *Darra,char *Carra)
int num = 0;
//记录式子中数字和运算符总数
//暂时存储，输入字符
//暂时存储，输入数字
Stack&char&
//存储运算符
bool wchar =
//是否有非法字符
cout&&&请输入表达式（为了方便可以带空格），并以'='号结束:\n&&&
while( cin&&ch, '='!=ch )
switch(ch)
cin.putback(ch);
//如果是数字，扔回去，用double型数据装
cout&&dou&&
//后缀表达式部分输出
Darra[num] =
(!mychar.Isempty()) &&
(mychar.Top()!='(') &&
//栈顶元素不是空括号
( (mychar.Top()=='*') || (mychar.Top()=='/') || (ch == '+') || (ch == '-') )
//栈顶运算符优先级不低于输入的运算符
//满足以上三个条件，将栈中元素全部弹出
cout&&mychar.Top()&&
//后缀表达式部分输出
Carra[num] = mychar.Top();
mychar.Pop();
mychar.Push(ch);
//若不满足，则将出入运算符压入栈中
尝试解决省略*的运算不成功
if('\0' == Carra[num] && num != 0)
cout&&'*'&&
Carra[num] = '*';
mychar.Push('(');
//遇到开括号压入栈
if(mychar.Isempty())
//判断括号是否匹配
cout&&&\n\n有多余的')'...&&&
return -1;
while(!mychar.Isempty())
//遇到闭括号，将栈中元素弹出
if('(' == mychar.Top())
//直至遇到开括号
mychar.Pop();
//如果栈为空，任然没有开括号，则执行弹出操作时，会出现错误，退出系统
cout&&mychar.Top()&& //后缀表达式部分输出
Carra[num] = mychar.Top();
mychar.Pop();
//检测非法字符
while(!mychar.Isempty())
//将栈中剩余运算符输出
if('(' == mychar.Top())
//括号不匹配
cout&&&\n\n有多余的'('...&&&
return -1;
cout&&mychar.Top()&&
//后缀表达式部分输出
Carra[num] = mychar.Top();
mychar.Pop();
if(0 == num)
//没有任何表达式输入
cout&&&\n\n您没有输入任何表达式...&&&
return -1;
cout&&&（字串中有非法字符）&;
cout&&endl&&&\n以上为中缀表达式和相应的后缀表达式，&;
运算函数，将储存在数组中的符号和数字（后缀表达式）取出，计算成结果返回
储存有后缀表达式的两个数组首地址（此处若用栈，则后缀表达式从栈中输出时，其顺序完全反相），后缀表达式的长度
返回值： 后缀表达式的计算结果
double Compute(char *Carra,double *Darra, int num)
int i = 1;
//取后缀表达式的辅助变量
double d1,d2;
//暂存栈中弹出的两个变量
Stack&double& R
//运算栈，储存数字
while( i &= num )
if(Carra[i] == '\0')
//如果i处是无效运算符，说明后缀表达式中，i处对应的应该是数字
Res.Push(Darra[i]);
//数字入栈
//如果是运算符
d1 = Res.Top();
Res.Pop();
d2 = Res.Top();
Res.Pop();
//从栈顶弹出两个数据进行计算
switch(Carra[i])
Res.Push(d1+d2);
//计算后压回栈
Res.Push(d2-d1);
Res.Push(d1*d2);
if(0 == d1)
cout&&&请注意分母不能为零...&&&
system(&pause&);
Res.Push(d2/d1);
cout&&&（Compute）运算符匹配出错了...&&&
return Res.Top();
//弹出栈中最后一个数字（计算结果）
int main()
double Darra[S_size];
//装入数据
char Carra[S_size];
//装入运算符
for(i=0; i&S_ i++)
//将储存运算符的数组做一个标记，以明确该下标所对应的是数字还是运算符
Carra[i] = '\0';
//若检测到Carra[i] = '\0',则说明Carra[i]中没有存入运算符，而Darra[i]中存储了一个数字
cout&&&*************************
一个简单表达式计算程序 *************************&&&
——by HQ&&&
cout&&&注意:请写全表达式,不要省略'*',写负数时请写成 '0 - x'的形式.\n&&&
if( ( i = change(Darra,Carra) )== -1 )
//判断转换是否成功
cout&&&\n转换失败...&&&
system(&pause&);
cout&&&其计算结果为:\n&&&
cout&&Compute(Carra,Darra,i)&&
//计算并输出结果
system(&pause&);
}stack.cpp
模板类（栈）的实现
#ifndef Stack_cpp
#define Stack_cpp
#include&Stack.h&
template&class T&
Stack&T&::Stack()
template&class T&
bool Stack&T&::Isempty()
// If the stack is empty, otherwise return false.
if(-1 == top)
template&class T&
void Stack&T&::Pop()
// Pop an element from the top of the stack
if(top == -1)
cout&&&弹出栈出错...&&&
template&class T&
void Stack&T&::Push(T ele)
// Push this element into the stack.
if(top & S_size)
cout&&&栈溢出...&&&
elem[top] =
template&class T&
T Stack&T&::Top()
// Return the top element of the stack.
if(-1 == top)
cout&&&已至栈底...&&&
//exit(0);
return elem[top];
template&class T&
int Stack&T&::Size()
//Return the number of the elements in the stack.
template&class T&
// clear all the elements in the stack
void Stack&T&::clear()
模板类（栈）
#ifndef Stack_h
#define Stack_h
#define S_size
//the size of the stack
template&class T&
class Stack
void Pop();
// Pop an element from the top of the stack
void Push(T elem);
// Push this element into the stack.
// Return the top element of the stack.
bool Isempty();
// If the stack is empty, otherwise return false.
int Size();
// Return the number of the elements in the stack.
void clear();
// clear all the elements in the stack
T elem[S_size];
运行结果：
参考知识库
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：134316次
积分：2260
积分：2260
排名：第15002名
原创：84篇
转载：22篇
评论：31条
(1)(2)(1)(1)(1)(1)(2)(2)(2)(3)(2)(5)(8)(3)(13)(9)(4)(5)(9)(4)(4)(1)(2)(2)(3)(16)(1)}