要進行一個表達式的計算,一個關鍵的就是括號匹配問題,現在使用棧進行實現計算表達式的值,可以作為實現一個簡單四則運算計算器核心部分。根據棧的特性(先進後出),所以決定通過把輸入的表達式轉換為後綴表達式,通過後綴表達式進行計算。
實現方法:
1.首先定義兩個棧,一個用於存放操作符,一個用於存放操作數。
1 #include<stdio.h>
2 #include<string>
3 #include<conio.h>
4 #define MAXSIZE 100
5 typedef float datatype;
6
7 typedef struct
8 {
9 datatype a[MAXSIZE];
10 int top;
11 }sequence_stack;
12
13 typedef struct
14 {
15 char b[MAXSIZE];
16 int top;
17 }SeqStack;
2.需要兩個數組,一個用於存放輸入的中綴表達式,一個用於存放將中綴表達式轉換後的後綴表達式。
將中綴表達式轉換為後綴表達式的主要代碼:
1 int operation(char op)//判斷是否為操作符
2 {
3 switch(op)
4 {
5 case'+':
6 case'-':
7 case'*':
8 case'/':return 1;
9 default:return 0;
10 }
11 }
12 int priority(char op)//判斷操作符的優先級
13 {
14 switch(op)
15 {
16 case'#':return -1;
17 case'(':return 0;
18 case'+':
19 case'-':return 1;
20 case'*':
21 case'/':return 2;
22 default: return -1;
23 }
24 }
25 //將中綴表達式轉換為後綴表達式
26 void postfix(char e[],char f[],SeqStack *s,sequence_stack *s1)
27 {
28 int i=0,j=0;
29 int t;
30 push_SeqStack(s,'#');
31 while(e[i]!='#')
32 {
33 if((e[i]>='0'&&e[i]<='9')||e[i]=='.')
34 f[j++]=e[i];
35 else if(e[i]=='(')
36 {
37 push_SeqStack(s,e[i]);
38 }
39 else if(e[i]==')')
40 {
41 t=s->top-1;
42 while(s->b[t]!='(')
43 {
44 f[j++]=s->b[--s->top];
45 t=s->top-1;
46 }
47 s->top--;
48 }
49 else if(operation(e[i]))
50 {
51 f[j++]=' ';
52 while(priority(s->b[s->top-1])>=priority(e[i]))
53 f[j++]=s->b[--s->top];
54 push_SeqStack(s,e[i]);
55 }
56 i++;
57 }
58 while (s->top)f[j++]=s->b[--s->top];
59 {}
60 evalpost(f,s1);
61 }
3.把存放後綴表達式的數組傳遞給計算後表達式的函數;
計算後綴表達式的值主要代碼:
1 float readnumber(char f[],int *i)//將數字字符串轉變為數
2 {
3 float x=0.0;
4 int k=0;
5 while(f[*i]>='0'&&f[*i]<='9')
6 {
7 x=x*10+(f[*i]-'0');
8 (*i)++;
9 }
10 if(f[*i]=='.')
11 {
12 (*i)++;
13 while(f[*i]>='0'&&f[*i]<='9')
14 {
15 x=x*10+(f[*i]-'0');
16 (*i)++;
17 k++;
18 }
19 }
20 while(k!=0)
21 {
22 x=x/10.0;
23 k=k-1;
24 }
25 return (x);
26 }
27 void evalpost(char f[],sequence_stack *s)
28 {
29 int i=0;
30 float x1,x2;
31 while(f[i]!='#')
32 {
33 if(f[i]>='0'&&f[i]<='9')
34 {
35 push_sequence_stack(s,readnumber(f,&i));
36 }
37 else if(f[i]==' ')
38 i++;
39 else if(f[i]=='+')
40 {
41 x2=s->a[--s->top];
42 x1=s->a[--s->top];
43 push_sequence_stack(s,x1+x2);
44 i++;
45 }
46 else if(f[i]=='-')
47 {
48 x2=s->a[--s->top];
49 x1=s->a[--s->top];
50 push_sequence_stack(s,x1-x2);
51 i++;
52 }
53 else if(f[i]=='*')
54 {
55 x2=s->a[--s->top];
56 x1=s->a[--s->top];
57 push_sequence_stack(s,x1*x2);
58 i++;
59 }
60 else if(f[i]=='/')
61 {
62 x2=s->a[--s->top];
63 x1=s->a[--s->top];
64 push_sequence_stack(s,x1/x2);
65 i++;
66 }
67 }
68 }
最後,只要調用計算後的結果將存放在操作數棧的第一個位置,並將結果傳遞給需要顯示的地方(可以放到自己的程序中顯示結果的地方),顯示出結果就沒問題了。注意傳入要計算的表達式,可用能想到任何方式。好了,就到這裡了。