栈（顺序栈）——算术表达式求值（计算）_用c语言程序顺序栈计算a*(b+c)+(d+e)

算术表达式求值由于我们输入的时中缀表达式，然而如果计算就需要转化成后缀表达式。

什么是中缀表达式？

例如 :a-(b+c*d)/e

例如 :a-(b+c*d)/e
这种算术表达式中的运算符总是出现在这两个操作数之间，这种算术表达式就是中缀表达式

什么是后缀表达式？

转换成：abcd*+e/-

后缀表达式与中缀表达式的操作数出现顺序相同，只是运算符先后顺序改变了。
后缀表达式不出现括号。

// 算术.h

#include<stdio.h>
#define StatckSize 100
#define false 0
#define true 1

typedef char DataType;
//定义顺序栈
typedef struct{
	DataType stack[StatckSize];
	int top;//栈顶指针   	起始值为0新增一个数栈顶 均加1 
}SeqStack; 


//顺序栈初始化
void InitStack(SeqStack *S);
//判断栈是否为空
int StackEmpty(SeqStack S);
//取栈顶元素
int GetTop(SeqStack S,DataType *e);
//进栈操作
int PushStack(SeqStack *S,DataType e);
//出栈操作
int PopStack(SeqStack *S,DataType *e);
//中缀表达式转换成后缀表达式
void TranslateExpress(char str[],char exp[]);



//顺序栈初始化
void InitStack(SeqStack *S){
		S->top=0;//把栈顶指针位置为0 
}

//判断栈是否为空
int StackEmpty(SeqStack S){
	if(S.top==0){
		return 1;
	} else{
		return 0;
	}
} 
 
//取栈顶元素
int GetTop(SeqStack S,DataType *e){
	if(S.top<=0)
	{
		printf("栈已经空\n");
		return 0; 
	}else{
		*e=S.stack[S.top-1];
		return 1;
	}
} 

//进栈操作
int PushStack(SeqStack *S,DataType e){
	if(S->top >= StatckSize)			//进栈前 ，判断是否栈已经满了
	{
		printf("栈已满，进栈失败\n");
		return 0; 
	}else{
		S->stack[S->top]=e;
		S->top++;
		return 1;
	}
}

//出栈操作
int PopStack(SeqStack *S,DataType *e){
	if(S->top==0)
	{
		printf("栈已经没有元素，不能出栈");
		return 0;
	}else{
		S->top--;
		*e=S->stack[S->top];
		return 1;
	}
} 

//中缀表达式转换成后缀表达式
void TranslateExpress(char str[],char exp[]){
	SeqStack S;      //  a           b 
	char ch;
	DataType e;
	int i=0,j=0;
	InitStack(&S);
	ch=str[i];//获取输入的第一个数或符号 
	i++;
	while(ch!='\0')
	{
			//case  进栈均是 算术符号 
		switch(ch)
		{
			case '(':
				PushStack(&S,ch);//进栈操作 
				break;
			case ')' :         //取栈顶元素    
				while(GetTop(S,&e)&&e!='(')
				{
					PopStack(&S,&e);
					exp[j]=e;
					j++;
				}
				PopStack(&S,&e);//当遇到（时，将符号插入栈中；当遇到）时，将（取出栈 
				break;
			case '+':
			case '-':
				while(!StackEmpty(S)&& GetTop(S,&e)&&e!='(')
				{
					PopStack(&S,&e);
					exp[j]=e;
					j++;
				}
				PushStack(&S,ch);//将当前运算符进栈
				break;
			case '*':
			case '/':
				while(!StackEmpty(S)&& GetTop(S,&e)&&e=='/'||e=='*')
				{
					PopStack(&S,&e);
					exp[j]=e;
					j++;
				}
				PushStack(&S,ch);//将当前运算符进栈
				break;
			case ' ':
				break;
			default:
				while(ch>='0'&&ch<='9')
				{
					exp[j]=ch;  //b 
					j++;
					ch=str[i];  //a 
					i++;
				}
				i--;
				exp[j]=' ';
				j++;
		}
		ch=str[i];
		i++;
	}
	while(!StackEmpty(S))
	{
		PopStack(&S,&e);
		exp[j]=e;
		j++;
	}	
	exp[j]='\0';
}
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
141
142
143
144
145
146
147
148
149
150
151

// 算术main.cpp

#include<stdio.h>
#include <cstdlib>
#include"算术.h"
#define MaxSize 50
typedef char DataType;
typedef struct {
	float data[MaxSize];
	int top;
}OpStack;

//计算后缀表达式
float ComputeExpress(char a[]);
//中缀表达式转换成后缀表达式
void TranslateExpress(char str[],char exp[]);

//计算后缀表达式
float ComputeExpress(char a[]){
	OpStack S;
	int i=0,value;
	float x1,x2;
	float result;
	S.top= -1;
	while(a[i]!='\0')
	{
		if(a[i]!=' ' && a[i]>='0'&& a[i]<='9')
		{
			value=0;
			while(a[i]!=' ')
			{
				value=10*value+a[i] -'0';
				i++;
			} 
			S.top++;
			S.data[S.top]=value;
		}else
		{
			switch(a[i])
			{
				case '+':
					x1=S.data[S.top];
					S.top--;
					x2=S.data[S.top];
					S.top--;
					result=x1+x2;
					S.top++;
					S.data[S.top]=result;
					break;
				case '-':
					x1=S.data[S.top];
					S.top--;
					x2=S.data[S.top];
					S.top--;
					result=x2-x1;
					S.top++;
					S.data[S.top]=result;
					break;
				case '*':
					x1=S.data[S.top];
					S.top--;
					x2=S.data[S.top];
					S.top--;
					result=x1*x2;
					S.top++;
					S.data[S.top]=result;
					break;
				case '/':
					x1=S.data[S.top];
					S.top--;
					x2=S.data[S.top];
					S.top--;
					result=x2/x1;
					S.top++;
					S.data[S.top]=result;
					break; 
			}
			i++;
		}
	 } 
	 if(S.top!=-1){
	 	result=S.data[S.top];
	 	S.top--;
	 	if(S.top==-1)
	 		return result;
	 	else
	 	{
	 		printf("表达式错误");
			exit(-1); 
		}
	 } 
}

//执行主函数
int main() {
	char a[MaxSize],b[MaxSize];
	float f;
	printf("请输入一个算术表达式：\n");
	gets(a);
	printf("中缀表达式：%s \n" ,a);
	TranslateExpress(a,b);
	printf("后缀表达式 %s \n" ,b);
	f=ComputeExpress(b);
	printf("计算结果： %.2lf \n",f);
	return 0;
}




 
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