#include"suffix.h"
int initList(SqList &l)
{
//构造一个空的线性表l
l.listbase=(elemType *)malloc(LIST_INIT_SIZE * sizeof(elemType));
if(!l.listbase)
{
exit(-1);
}
l.length=0;
l.listsize=LIST_INIT_SIZE;
return 0;
}
void listInsert(SqList &l)
{
char ch;
int w;
int i=0;
/*while(l.length<7)
{
printf("请输入运算符:");
scanf("%c", &ch);
printf("请输入%c的权值:", ch);
scanf("%d", &w);
getchar();
l.listbase[i].op=ch;
l.listbase[i].weight=w;
l.length++;
i++;
}*/
l.length=7;
l.listbase[0].op='#';
l.listbase[0].weight=-1;
l.listbase[1].op='(';
l.listbase[1].weight=0;
l.listbase[2].op=')';
l.listbase[2].weight=0;
l.listbase[3].op='+';
l.listbase[3].weight=1;
l.listbase[4].op='-';
l.listbase[4].weight=1;
l.listbase[5].op='*';
l.listbase[5].weight=2;
l.listbase[6].op='/';
l.listbase[6].weight=2;
}
void display(SqList l)
{
for(int i=0; i<l.length; i++)
{
printf("运算符%2c的权值为:%3d", l.listbase[i].op, l.listbase[i].weight);
printf("\n");
}
}
int locate(SqList l, char ch, int (* fun)(char, char))
{
//在顺序线性表中查找第一个值与ch满足fun()的元素的下标
//若找到,则返回其在线性表中的下标,否则返回-1
int i=0;//i的初值为第一个元素的下标
while((i<l.length) && !(* fun)(l.listbase[i].op, ch))
{
i++;
}
if(i<l.length)
{
return i;
}
else
{
return -1;
}
}
int compare(char a, char b)
{
return (a==b)? 1: 0;
}
//顺序栈类型的定义
void initStack(stack &s)
{
s.stackbase=(char *)malloc(STACK_INIT_SIZE * sizeof(char));
if(!s.stackbase)//存储空间分配失败
{
exit(1);
}
s.stacksize=STACK_INIT_SIZE;
s.top=0;//空栈的栈顶指针为0
}
bool getTop(stack s, char &e)
{
//若栈不空,则用e返回栈顶元素,并返回true;
//否则返回false
if(s.top == 0)
{
return false;
}
e=*(s.stackbase+s.top-1);//返回非空栈中栈顶元素
return true;
}
bool push(stack &s, char e)
{
//若栈的存储空间不满,则插入元素e,
//e为新的栈顶元素,并返回true;
if(s.top == s.stacksize)//栈已满
{
char * newbase;
newbase=(char *)realloc(s.stackbase, (s.stacksize+STACKINCREMENT)*sizeof(char));
if(!newbase)
{
exit(1);
}
s.stackbase=newbase;
s.stacksize+=STACKINCREMENT;
}
*(s.stackbase+s.top)=e;//插入新元素
s.top++;//栈顶指针后移
return true;
}
bool pop(stack &s, char &e)
{
//若栈不空,则删除栈顶元素,用e返回其值,
//并返回true;否则返回false
if(s.top == 0)
{
return false;
}
e=*(s.stackbase+s.top-1);//返回非空栈中栈顶元素
s.top--;//栈顶指针前移
return true;
}
void transform(char suffix[], char exp[], SqList l)
{
//从合法的表达式字符串exp求得其相应的后缀式suffix
stack s;
initStack(s);
push(s, '#');
char * p;
p=exp;
char ch=* p;
int i=0;
char e;
int loc;
while(s.top!=0)
{
loc=locate(l, ch, compare);
if(loc == -1)
{
suffix[i++]=ch;
}
else
{
switch(ch)
{
case '(':
push(s, ch);
break;
case ')':
{
pop(s, e);
while(e != '(')
{
suffix[i++]=e;
pop(s, e);
}
break;
}
default:
{
int s1;
int s2=locate(l, ch, compare);
//loc
int flag=1;
while(flag)
{
getTop(s, e);
s1=locate(l, e, compare);
if(l.listbase[s1].weight>l.listbase[s2].weight)
{
pop(s, e);
suffix[i++]=e;
}
else
{
flag=0;
}
}//while(flag)
if(ch != '#')
{
push(s, ch);
}
break;
}//default
}//switch
}//else
if(ch != '#')
{
p++;
ch=* p;
}
else
{
suffix[i]=ch;
break;
}
}//while
}//transform
将原表达式转换成后缀表达式——表达式求值问题
需积分: 16 34 浏览量
2009-04-18
21:57:39
上传
评论
收藏 180KB RAR 举报
Sabrina0115
- 粉丝: 7
- 资源: 26
最新资源
- STM32单片机FPGA毕设电路原理论文报告一种基于st62单片机的称重显示控制器
- STM32单片机FPGA毕设电路原理论文报告一种基于SPCE061A单片机的信号发生器
- Ruby菜鸟入门指南.md
- STM32单片机FPGA毕设电路原理论文报告一种基于PIC系列单片机的SPWM逆变电源
- exp01A.cpp
- Rust语言学习万字指南!.md
- STM32单片机FPGA毕设电路原理论文报告一种基于msp430单片机的心电模块设计
- STM32单片机FPGA毕设电路原理论文报告一种基于MSP430单片机的日程管理系统
- web-screen-capture.jar
- 2024最新计算机二级真题练习题库含答案.md
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈