0%

链栈 表达式运算

第二次数据结构实验

用链栈来储存OPND和OPTR,只能计算个位的运算且结果也是个位

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
#include<stdio.h> 
#include<string.h>
#include<stdlib.h>

#define OK 1
#define ERROR 0
#define OVERFLOW -2
typedef char SElemType;
typedef char ElemType;
typedef int Status;

typedef struct StackNode{
SElemType data;
struct StackNode *next;
}StackNode,*LinkStack;

LinkStack OPND,OPTR;//创建运算符栈和操作数栈

Status InitStack(LinkStack &S){
S=NULL; //构造一个空栈S,栈顶指针置空
return OK;
}

Status Push(LinkStack &S, SElemType e){
LinkStack p;
p=new StackNode; e
p->data=e; //在栈顶插入元素
p->next=S; //p指向S
S=p; //p作为栈顶
return OK;
}

Status Pop(LinkStack &S,SElemType &e){
LinkStack p; //删除S的栈顶元素,用e返回其值
if(S==NULL) return ERROR;
e=S->data;
p=S;
S=S->next;
delete p;
return OK;
}

SElemType GetTop(LinkStack S)
{//返回S的栈顶元素,不修改栈顶指针
if(S!=NULL)
return S->data;
}
Status In(char ch){ //判断ch是否为运算符
if(ch<='9'&&ch>='0')
return ERROR; //不是运算符
else
return OK;
}
SElemType Precede(SElemType ch1,SElemType ch2){
//比较操作符号的优先级
switch(ch1){
case '+':
if(ch2=='+'||ch2=='-'||ch2==')'||ch2=='#') return '>';
else return '<';
case '-':
if(ch2=='+'||ch2=='-'||ch2==')'||ch2=='#') return '>';
else return '<';
case '*':
if(ch2=='(') return '<';
else return '>';
case '/':
if(ch2=='(') return '<';
else return '>';
case '(':
if(ch2==')') return '=';
else return '<';
case ')':
return '>';
case '#':
if(ch2=='#') return '=';
else return '<';
}
}
SElemType Operate(SElemType a,SElemType theta,SElemType b){
//计算a运算符b的值
SElemType res;
a = a - '0';
b = b - '0';
switch(theta){
case '+':
res = a + b +'0';
break;
case '-':
res = a - b + '0';
break;
case '*':
res = a * b +'0';
break;
case '/':
res = a / b +'0';
break;
}
return res;
}
int EvaluateExpression(){
char ch,a,b,x;
char theta;
if(InitStack(OPND)) puts("操作数栈初始化成功");
if(InitStack(OPTR)) puts("操作符栈初始化成功");
Push(OPTR,'#');
ch=getchar();
while(ch!='#'||GetTop(OPTR)!='#')
{
if(!In(ch)) { //ch不是运算符
Push(OPND,ch);
ch=getchar();
}
else
switch(Precede(GetTop(OPTR),ch))
{
case '<':
Push(OPTR,ch);
ch=getchar();
break;
case '>':
Pop(OPTR,theta);
Pop(OPND,b);
Pop(OPND,a);
Push(OPND,Operate(a,theta,b));
break;
case '=':
Pop(OPTR,x);
ch=getchar();
break;
}
}
return GetTop(OPND)-'0';
}
int main()
{
printf("请输入算数表达式(最后以#结束):");
printf("形如 2*(2-1)# \n") ;
printf("%d",EvaluateExpression());
return 0;
}