songsong的垃圾堆

收废铜烂铁~

0%

栈的应用--数值转换与表达式求值

发表于 更新于 阅读： Valine：
本文字数： 1.4k 阅读时长 ≈ 5 分钟

1.数值转换

原理大家肯定都知道，就除K取余，直到商为0时，倒序输出余数即为转换后的K进制数。一说倒序，就很符合栈（Last In First Out，LIFO）“后进先出”的思想。
这个简单，直接上代码：

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
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define MAX 100//定义栈的最大值 

typedef int ElemType;

typedef struct{
	ElemType base[MAX];
	int top;
}SqStack;

SqStack SqStackInit(){//初始化栈 
	SqStack S;
	S.top=-1;
	return S;
}

int StackEmpty(SqStack S){//判断栈空 
	if(S.top==-1){
		return 1;
	}
	else return 0;
}

SqStack SqStackPush(SqStack S,ElemType x){//入栈 
	if(S.top==MAX-1){
		printf("栈满了");
		return S;
	}
	S.top++;
	S.base[S.top]=x;
	return S;
}

ElemType GetSqStackTop(SqStack S){//获取栈顶元素 
	return (S.base[S.top]);
}

SqStack SqStackPop(SqStack S,ElemType *x){//出栈 
		if(StackEmpty(S)){
			printf("栈空了"); 
			return S;
	    }
		*x=S.base[S.top];
		S.top--;
		return S;
}

void Fprintf(int m){		//转换进制后能显示ABC等
	if(m<10){
		printf("%d",m);
		return;
	}
	else{
		char c=m-10+'A';
		printf("%c",c);
		return;
	}
}

void solve(int n,int r){
	int m;
	SqStack ss=SqStackInit();
	while(n>=r){
		m=n%r;
		n=n/r;
		ss=SqStackPush(ss,m);
	}
	ss=SqStackPush(ss,n);
	while(!StackEmpty(ss)){
		int m=GetSqStackTop(ss);
		ss=SqStackPop(ss,&m);
		Fprintf(m);
	}
	printf("\n");
}

int main(){
	//测试 
//	int a[5];
//	cout<<"请输入5个整数构成一个栈" <<endl;
//	for(int i=0;i<5;i++){
//		cin>>a[i];
//	} 
//	SqStack s=SqStackInit();
//	cout<<"现在将初始化一个栈！"<<endl;
//	if(StackEmpty(s)){
//		cout<<"栈空"<<endl;
//	}
//	else cout<<"栈非空"<<endl;
//	cout<<"现在将上面的元素入栈"<<endl;
//	for(int i=0;i<5;i++){
//	 	s=SqStackPush(s,a[i]);
//	 }
//	cout<<"现在将依次出栈"<<endl;
//	for(int i=0;i<5;i++){
//	 	cout<<"栈顶元素"<<GetSqStackTop(s)<<endl;
//	 	s=SqStackPop(s,&s.top);
//	 }	
//	if(StackEmpty(s)){
//		cout<<"栈空"<<endl;
//			}  
//		else cout<<"栈非空"<<endl;
	int n,r;
	printf("请输入一个整数和要转换的进制数\n");
	
	while(scanf("%d %d",&n,&r)){
		solve(n,r);
		printf("请输入一个整数和要转换的进制数\n");
	} 
	return 0; 
}

运行结果：

在这里插入图片描述
回到目录

2.表达式求值

如果学过编译原理，这个是比较好理解的。

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
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>              // 内含isdigit()函数
#include <string.h>         
#define STACK_INIT_SIZE 100     // 栈容量
#define STACK_INCREMENT 10      // 栈增量

typedef float DATATYPE;
typedef char SYMBOLTYPE;

typedef struct stack
{
    int *base;         		// 基地址
    int *top;          		// 栈顶指针
    int stackSize;          // 栈容量
}*Stack,LinkStack;


// 栈的初始化
Stack Init_Stack(Stack S)
{
    S=(Stack)malloc(sizeof(Stack));
    if(!S)
        exit(0);
        
    S->base = (int*)malloc(STACK_INIT_SIZE*sizeof(DATATYPE));

    if(!S->base)
        exit(0);

    S->top = S->base;
    S->stackSize = STACK_INIT_SIZE;
    return S;
}

// 判栈空
int IsEmpty(Stack S)
{
//    if (S->top == S->base){
//        return 1;
//    } 
//	else{
//        return 0;
//    }
    return (S->top==S->base ? 1:0);
}

// 判栈满
int IsFull(Stack S)
{
//    if (S->top - S->base == S->stackSize) {
//        return 1;
//    } 
//	else{
//        return 0;
//
//    }
    return (S->top - S->base == S->stackSize ? 1:0);
}

// 操作数压栈
void Push(Stack S, DATATYPE e)
{
    if (IsFull(S))

    {

        S->base = (int*)malloc((STACK_INIT_SIZE+STACK_INCREMENT)*sizeof(DATATYPE));

        if (!S->base)

            exit(0);        // 存储分配失败

        S->top = S->base + S->stackSize;

        S->stackSize += STACK_INCREMENT;

    }

    *S->top++ = e;

}

// 运算符压栈
void PushSymbol(Stack S, SYMBOLTYPE e)
{
    if (IsFull(S))
    {
        S->base = (int*)malloc((STACK_INIT_SIZE+STACK_INCREMENT)*sizeof(DATATYPE));

        if (!S->base)
            exit(0);        // 存储分配失败

        S->top = S->base + S->stackSize;
        S->stackSize += STACK_INCREMENT;
    }
    *S->top++ = e;
}


// 操作数弹栈
DATATYPE Pop(Stack S)
{
    if (S->top == S->base)
        return 0;              // 空栈弹出0保证部分负数的正确运算
    else
    {
        return *--S->top;     // *--S->top就是*(--S->top)
    }
} 

// 运算符弹栈
SYMBOLTYPE PopSymbol(Stack S)
{
    if (S->top == S->base)
        return 0;
    else{
        return *--S->top;
    }
}

// 栈的销毁
void DestroyStack(Stack S) {
    free(S->base);
	free(S);
}

// 运算符优先级表
char Priority[7][7] =		   //行row（左边的）是栈顶运算符，列col（上边的）是入栈运算符
{       				 	
		 // '+' '-' '*' '/' '(' ')' '#'   			
    {/*'+'*/'>','>','<','<','<','>','>'},

    {/*'-'*/'>','>','<','<','<','>','>'},

    {/*'*'*/'>','>','>','>','<','>','>'},

    {/*'/'*/'>','>','>','>','<','>','>'},

    {/*'('*/'<','<','<','<','<','=','0'},

    {/*')'*/'>','>','>','>','0','>','>'},

  	{/*'#'*/'<','<','<','<','<','0','='}
};

// 确定运算符所在的行数或列数
int Operator(char c)
{
    switch(c)
    {
        case '+': return 0;
        case '-': return 1;
        case '*': return 2;
        case '/': return 3;
        case '(': return 4;
        case ')': return 5;
        case '#': return 6;
        default:  return -1;
    }

}

 
// 计算弹出的两个操作数与弹出栈顶运算符的值
float Calculation(float a, char op, float b)
{
    switch(op)
    {
        case '+': return a+b;
        case '-': return a-b;
        case '*': return a*b;
        case '/': return a/b;
        default:  return -1;
    }
}

// 表达式求值函数
float CalculatingExpression(char *s)
{
    int i;  
    strcat(s, "#");                 				// 为表达式s串接"#"
    Stack OPND=NULL;
    OPND = Init_Stack(OPND);       					// 创建操作数栈
    
    Stack OPTR=NULL;
    OPTR = Init_Stack(OPTR);       					// 创建运算符栈

    PushSymbol(OPTR, '#');          				//"#"压栈作为运算符栈的栈底元素

    for (i=0; i<strlen(s); i++)
    {
        while(s[i]==' ')            				// while循环跳过空格
            i++;
 
        if (isdigit(s[i]))         					// 判断是否是数字
        {
            int j=i;
            i++;
            while(isdigit(s[i]))        			// 确定是几位数
            {
               i++;
            }                  
			char str[10]="";
  			if (!isdigit(s[i]))     				// 此时的i应该指向一个运算符(包括#) 
            {		 
	            for (;j<i;j++)          			// 将字符串数组下标j到i的数字字符转换为字符串
	            {
	                char c[2] = {s[j]};
	                strcat(str, c);
	            }
	            i--;								//如果不减1，for循环里的i++则跳过了运算符
            }           

            float operand = atof(str);  			// 将字符串转换为浮点数
            Push(OPND, operand);        			// 浮点数压入操作数栈
        }
        else {										// 不是数字，就是操作符了 

            int row = Operator(*(OPTR->top-1)), 	// 确定栈顶运算符的行数
				col = Operator(s[i]);       		// 确定入栈运算符的列数

            switch(Priority[row][col])              // 确定优先级
            {

                case '<': PushSymbol(OPTR, s[i]); break;

                case '>': Push(OPND, Calculation(Pop(OPND), PopSymbol(OPTR), Pop(OPND))); --i; break;       

                             //Push()参数里右边的Pop先执行；--i是为了下次继续对当前入栈运算符s[i]进行判断

                case '=': PopSymbol(OPTR); break;

                default:  printf("输入错误，请检查数字之间是否有空格，表达式是否正确！\n");

                          DestroyStack(OPTR);

                          DestroyStack(OPND);

                          return -1;           // 运行到这一步，说明表达式错误

            }

        }

    }

    DestroyStack(OPTR);

    return Pop(OPND);       // 运行到这一步，说明表达式正确，弹出操作数栈的值即为运算结果
}

int main()
{

    char s[100];

    printf("请输入要计算的表达式：\n");

    gets(s);

    printf("表达式 %s 的值为：\n", s);

    printf("%1.2f", CalculatingExpression(s));

    return 0;

}

运行结果：

注意：“/”，做的是取商操作，不是“÷”。
在这里插入图片描述
回到目录

------------- Thank you for reading -------------
Title - Artist
0:00