实验三 栈和队列的基本操作及应用
——表达式求值
实验目的
（1）掌握栈“后进先出”的特点。
（2）掌握栈的典型应用——表达式求值。
实验要求
（1）分析算符优先算法进行表达式求值的算法思想，用C语言设计程序。
（2）上机调试通过实验程序。
（3）给出具体的算法分析，包括时间复杂度和空间复杂度等。
（4）撰写实验报告。
实验内容
（1）设立两个栈，一个操作数栈，一个操作符栈。开始时，操作数栈空，操作符栈压入’#’。用键盘输入一个整数运算表达式（操作数的范围是0～9，运算符只含+、-、*、/、（、）、#，而且中间不可以有空格），使用循环程序从左向右读入表达式。
（2）如果读入的是操作数，直接进入操作数栈。
（3）如果读入的是运算符c，则和操作符栈的栈顶运算符t比较优先权后作相应操作：
c>t：c进OPTR栈；
c<t：退操作符栈，二次退操作数栈，将计算结果进操作数栈；
c<t：退OPTR栈（脱括号）
直到读入‘#’为止。
（4）检验程序运行结果。
实验部分代码
typedef struct intstack{
int data[MAXSIZE];
int top;
}intStack;
//初始化栈
void initstack(intStack&s){
s.top=0;
}
//判断栈空
int stackempty(intStack&s){
if(s.top==0)
return 1;
else
return 0;
}
//取栈顶元素
int getTop(intStack s)
{
}
//入栈操作
void push(intStack&s,int i){
}
//出栈操作
int pop(intStack&s){
}
//另外仿照这个整数栈，写出操作符栈的定义和栈的操作。
//判断字符c是否是运算符，若是返回1，否则返回0
int In(char s,char op[])
{
}
/*判断两个字符s1和s2的优先级，如果s1优先级高于s2，则返回>,两者优先级相等返回=，否则返回>*/
char precede(char s1,char s2)
{
}
//计算a theta b的值，将结果返回
int Operate(a,theta,b)
{
}
//表达式求值compute
int compute(char exp[])
{
}
//主函数
void main(){
int p=0,i=0;
char str[100];
printf("请输入以#号为结束的表达式(只包含+,-,*,/,(,))：\n");//输入计算的表达式以#作为结束标志
scanf("%c",&str[p]);
while(str[p]!='#')//对输入字符进行判断直至输入#
{
p++;
scanf("%c",&str[p]);
}
printf("输入表达式为：");
for(i=0;i<p;i++)
printf("%c",str[i]);
printf("\n");
printf(“%d\n”,compute(str));
}
#include "stdafx.h"
#include "string.h"
#define N -1
#include <malloc.h>
#define LEN sizeof(struct student)
struct student
{
int num; //表达式的值
char date; //表达式的符号
struct student * next;
};
struct student *head1() //得到栈表达式中数据的top指针
{
struct student *p1;
p1=(struct student*)malloc(sizeof(struct student));
p1->next=NULL;
return p1;
}
void get1(struct student *p1) //p1相当于top,建立表达式数据的栈
{
struct student *top,*h;
int x;
top=p1; //p2相当于单链表的头结点
printf("请输入你的数据(该数据从左往右是依次算式的数字）,并在末尾输入-1以示结束\n");
scanf("%d",&x );
while(x!=N)
{
h=(struct student*)malloc(sizeof(struct student));
h->num=x;
h->next =top->next;
top->next=h; //生成新结点,将读入数据存放到新结点的数据域中,将该新结点插入到链表的前端
scanf("%d",&x );
}
}
struct student *head2() //得到栈表达式中字符的top指针
{
struct student *p2;
p2=(struct student*)malloc(sizeof(struct student));
p2->next=NULL;
return p2;
}
void get2(struct student *p2) //p1相当于top,建立表达式字符的栈
{
struct student *top,*h;
char x;
char b;
top=p2; //p2相当于单链表的头结点
printf("请输入你的数据(该数据是算式的运算符),并在末尾输入!以示结束\n");
scanf("%c",&x );
b=x;
while(b!='!')
{
h=(struct student*)malloc(sizeof(struct student));
h->date=x;
if(h->date==10)
{
h=(struct student*)malloc(sizeof(struct student));
scanf("%c",&x);
h->date=x;
h->next =top->next;
top->next=h;
}
else
{
h->next =top->next;
top->next=h; //生成新结点,将读入数据存放到新结点的数据域中,将该新结点插入到链表的前端
scanf("%c",&x );
}
b=h->date;
scanf("%c",&x);
}
top->next=top->next->next;
}
void put1(struct student *p1) //输出栈表达式的数据
{
struct student *p3;
p3=p1;
printf("数字栈中的数据有:\n");
while(p3->next!=NULL)
{
printf("%d",p3->next->num );
p3=p3->next;
if(p3->next!=NULL)
{
printf("->");
}
}
printf("\n");
}
void put2(struct student *p2) //输出栈表达式的数据
{
struct student *p3;
p3=p2;
printf("字符栈的数据有:\n");
while(p3->next!=NULL)
{
printf("%c",p3->next->date );
p3=p3->next;
if(p3->next!=NULL)
{
printf("->");
}
}
printf("\n");
}
int pop1(struct student *p1) //表达式数据弹栈
{
struct student *top,*p,*a;
top=p1;
int m;
m=top->next ->num ;
a=top->next ;
p=top->next ;
p=p->next ;
top->next =p;
delete a;
return m;
}
void push1(struct student *p1,int num) //表达式数据压栈
{
struct student *top,*n,*p;
top=p1;
n=(struct student*)malloc(sizeof(struct student));
n->num =num;
n->next=top->next ;
top->next =n;
p=top->next ;
while(p!=NULL)
{
printf("%d",p->num );
p=p->next;
if(p!=NULL)
{
printf("->");
}
}
printf("\n");
}
char pop2(struct student *p2) //表达式字符弹栈
{
struct student *top,*p,*a;
top=p2;
char m;
m=top->next ->date ;
a=top->next ;
p=top->next ;
p=p->next ;
top->next =p;
delete a;
return m;
}
void push2(struct student *p2,char date) //表达式字符压栈
{
struct student *top,*n,*p;
top=p2;
n=(struct student*)malloc(sizeof(struct student));
n->date =date;
n->next=top->next ;
top->next =n;
p=top->next ;
while(p!=NULL)
{
printf("%c",p->date );
p=p->next;
if(p!=NULL)
{
printf("||");
}
}
printf("\n");
}
int opreate(int num1,int num2,char num3)
{
int a,b,sum;
a=num1;
b=num2;
if(num3==43)
{
sum=a+b;
}
if(num3==95)
{
sum=b-a;
}
if(num3==42)
{
sum=a*b;
}
return sum;
}
int main()
{
struct student *top1,*top2;
char m,n,q;
int sum,a,b;
top1=head1(); //得到栈表达式的数据的栈顶指针
top2=head2(); //得到栈表达式的字符的栈顶指针
get1(top1); //建立表达式的数据栈
get2(top2); //建立表达式的字符栈
printf("请输入运算字符\n");
scanf("%c",&m);
while(m!='#')
{
n=pop2(top2);
if(n>m) //比较表达式字符栈的栈顶元素和输入的大小
{
push2(top2,n);
push2(top2,m);
printf("请输入运算字符\n");
scanf("%c",&m);
}
else if(n<m)
{
if(m==42||m==43||m==95)
{
a=pop1(top1);
b=pop1(top1);
push1(top1, opreate(a,b,m));
push2(top2,n);
scanf("%c",&m);
}
else
{
a=pop1(top1);
b=pop1(top1);
n=pop2(top2);
push1(top1, opreate(a,b,n));
scanf("%c",&m);
}
}
else if(n==m)
{
scanf("%c",&m);
}
scanf("%c",&m);
}
printf("%d",pop1(top1));
printf("\n");
return 0;
}
