RH.h
1 #ifndef _MRCHEN_RP_H_
2 #define _MRCHEN_RP_H_
3 #include "stdio.h"
4 #include "stdlib.h"
5 #include "malloc.h"
6 #include "string.h"
7 #include "iostream"
8 #include <stack>
9 using namespace std;
10 #ifndef __cplusplus
11 typedef int BOOL;
12 #ifndef TRUE
13 #define TRUE 1
14 #endif
15 #ifndef FALSE
16 #define FALSE 0
17 #endif
18 #else
19 typedef bool BOOL;
20 #ifndef TRUE
21 #define TRUE true
22 #endif
23 #ifndef FALSE
24 #define FALSE false
25 #endif
26 #endif
27
28 //用於子串連接的結構
29 typedef struct _tagSubExp{
30 char *exp_p;
31 struct _tagSubExp*next;
32 }SUB_EXP,*PSUB_EXP;
33
34 extern stack<PSUB_EXP> s1;//存放表達式
35 extern stack<PSUB_EXP> s2;//存放括號和運算符
36 /*子串出棧*/
37 BOOL pop_exp(PSUB_EXP*,BOOL);
38 /*子串入棧*/
39 BOOL push_exp(PSUB_EXP,BOOL);
40 /*合併三個子串*/
41 BOOL cat_exp(PSUB_EXP,PSUB_EXP,PSUB_EXP);
42 /*一次獲取中綴表達式中的子串*/
43 BOOL get_next(PSUB_EXP*,char*);
44 /*獲取中綴表達式*/
45 char * get_exp(char *exp_p);
46 /*將中綴表達式轉換為後綴表達式*/
47 char * convert_exp(char *exp,char *convert_sz);
48 /*打印逆波蘭表達式*/
49 void print_exp(PSUB_EXP);
50
51 #endif
RH.cpp
1 // 逆波蘭運算.cpp : Defines the entry point for the console application.
2 #include "stdafx.h"
3 #include "RP.h"
4
5 stack<PSUB_EXP> s1;
6 stack<PSUB_EXP> s2;
7
8 /*打印後綴表達式*/
9 void print_exp(PSUB_EXP p)
10 {
11 while(p){
12 printf("%s ",p->exp_p);
13 p = p->next;
14 }
15 printf("\n");
16 }
17
18 /*將中綴表達式轉換為後綴表達式*/
19 char * convert_exp(char *exp,char *convert_p)
20 {
21 char ch;
22 PSUB_EXP p;
23 PSUB_EXP sub_p;
24 PSUB_EXP f_p, s_p, t_p;
25 //判斷參數時候合法
26 if(convert_p==NULL||exp==NULL || *exp == '\n'){
27 return NULL;
28 }
29 //循環讀取中綴表達式
30 while( TRUE==get_next(&sub_p,exp) ){
31 //判斷讀取到的是數字串還是運算符還是括號
32 ch = *(sub_p->exp_p);
33 switch(ch){
34 //如果是 + ， 則入棧
35 case '+':
36 {
37 push_exp(sub_p,FALSE);
38 }
39 break;
40 //如果是 - ， 則入棧
41 case '-':
42 {
43 push_exp(sub_p,FALSE);
44 }
45 break;
46 //如果是 * ， 則入棧
47 case '*':
48 {
49 //先入棧
50 push_exp(sub_p,FALSE);
51 //然後讀取下個字串
52 get_next(&sub_p,exp);
53 //如果是數字串，這進行合併處理
54 ch = *(sub_p->exp_p);
55 if(ch >= '0' && ch <= '9' ){
56 s_p = sub_p;
57 pop_exp(&t_p,FALSE);
58 pop_exp(&f_p,TRUE);
59 cat_exp(f_p,s_p,t_p);
60 push_exp(f_p,TRUE);
61 }else if(ch == '('){//如果是括號，則入棧
62 push_exp(sub_p,FALSE);
63 }
64 }
65 break;
66 case '/':
67 {
68 //先入棧
69 push_exp(sub_p,FALSE);
70 //然後讀取下個字串
71 get_next(&sub_p,exp);
72 //如果是數字串，這進行合併處理
73 ch = *(sub_p->exp_p);
74 if(ch >= '0' && ch <= '9' ){
75 s_p = sub_p;
76 pop_exp(&t_p,FALSE);
77 pop_exp(&f_p,TRUE);
78 cat_exp(f_p,s_p,t_p);
79 push_exp(f_p,TRUE);
80 }else if(ch == '('){//如果是括號，則入棧
81 push_exp(sub_p,FALSE);
82 }
83 }
84 break;
85 case '('://如果是前括號 則入棧
86 {
87 push_exp(sub_p,FALSE);
88 }
89 break;
90 case ')'://如果是否括號，這進行相應處理
91 {
92 //從棧中彈出兩表達式串，一個運算符串，然後合併並押入棧中，直到彈出的運算符是 '('
93 while(pop_exp(&t_p,FALSE)&&*(t_p->exp_p)!='('){
94 pop_exp(&s_p,TRUE);
95 pop_exp(&f_p,TRUE);
96 cat_exp(f_p,s_p,t_p);
97 push_exp(f_p,TRUE);
98 }
99 //接着彈出後續的運算符
100 pop_exp(&t_p,FALSE);
101 //如果是 * 或 / , 則再從棧中彈出兩表達式，併合並 然後入棧
102 if(*(t_p->exp_p)=='*'||*(t_p->exp_p)!='/'){
103 pop_exp(&s_p,TRUE);
104 pop_exp(&f_p,TRUE);
105 cat_exp(f_p,s_p,t_p);
106 push_exp(f_p,TRUE);
107 }else{//如果不是 * 或 / , 則將運算符方入棧中
108 push_exp(t_p,FALSE);
109 }
110 }
111 break;
112 default:
113 {//如果是數字串 ， 則 入棧
114 push_exp(sub_p,TRUE);
115 }
116 break;
117 }
118 }
119 //將棧中剩下的數據排列成後綴形式
120 while(pop_exp(&t_p,FALSE)){
121 pop_exp(&s_p,TRUE);
122 pop_exp(&f_p,TRUE);
123 cat_exp(f_p,s_p,t_p);
124 push_exp(f_p,TRUE);
125 }
126 //將轉換好的後綴表達式存放到新的空間中
127 while(f_p){
128 strcat(convert_p,f_p->exp_p);
129 p = f_p;
130 f_p = f_p->next;
131 getchar();
132 free(p);
133 }
134 return convert_p;
135 }
136
137 /*獲取中綴表達式*/
138 char* get_exp(char *exp_p)
139 {
140 char tmp_exp_sz[64+1];
141 char *p = tmp_exp_sz;
142 int i;
143 //輸入中綴表達式
144 fgets(p,64,stdin);
145 //然後解析中綴表達式 ， 並以 '\0'分割每個子串
146 for(i=0; *p!='\0' ; i++){
147 if(*p >= '0' && *p <= '9'){
148 exp_p[i] = *p;
149 }else{
150 if(*p != ' '){
151 exp_p[i++] = NULL;
152 exp_p[i++] = *p;
153 exp_p[i] = NULL;
154 }
155 }
156 p++;
157 }
158 return 0;
159 }
160 /*一次獲取中綴表達式中的子串*/
161 BOOL get_next(PSUB_EXP * sub_p,char*exp_p)
162 {
163 static char *p = exp_p;
164 if(*p == '\n'){
165 return FALSE;
166 }
167 //申請保存串信息的節點
168 *sub_p = (PSUB_EXP)calloc(1,sizeof(SUB_EXP));
169 (*sub_p)->exp_p = p;
170 //獲取下一個串
171 p += strlen(p);
172 while(*(++p) == NULL);
173 return TRUE;
174 }
175
176 /*子串出棧*/
177 BOOL pop_exp(PSUB_EXP* sub_pp,BOOL flag)
178 {
179 if(flag == TRUE){// 從s1棧中彈出表達式串
180 if(s1.empty())
181 return FALSE;
182 *sub_pp = (PSUB_EXP)s1.top();
183 s1.pop();
184 }else{//從s2中彈出運算符串
185 if(s2.empty())
186 return FALSE;
187 *sub_pp = (PSUB_EXP)s2.top();
188 s2.pop();
189 }
190 return TRUE;
191 }
192
193 /*子串入棧*/
194 BOOL push_exp(PSUB_EXP sub_p,BOOL flag)
195 {
196 if(flag == TRUE){//如果是表達式串則放入s1棧中
197 s1.push(sub_p);
198 }else{
199 s2.push(sub_p);//如果是表達式串則放入s2棧中
200 }
201 return TRUE;
202 }
203
204 /*合併三個子串*/
205 BOOL cat_exp(PSUB_EXP f_p,PSUB_EXP s_p,PSUB_EXP t_p)
206 {
207 PSUB_EXP p;
208 if(!f_p || !s_p || !t_p){
209 return FALSE;
210 }else{
211 //按 f_p:s_p:t_p 的順序合併
212 p = f_p;
213 while(p->next)
214 p = p->next;
215 p->next = s_p;
216 p = s_p;
217 while(p->next)
218 p = p->next;
219 p->next = t_p;
220 }
221 return TRUE;
222 }
main.cpp
1 // 逆波蘭運算.cpp : Defines the entry point for the console application.
2 #include "stdafx.h"
3 #include "RP.h"
4 //9+20*(15-4)+7/8-6
5 int main(int argc, char* argv[])
6 {
7 char exp_sz[128+1] = {0};
8 char convert_sz[128+1] = {0};
9 char *p = exp_sz;
10 get_exp(exp_sz);
11 /*
12 while( *p!= '\n'){
13 puts(p);
14 p += strlen(p);
15 while(*(++p)==NULL);
16 }
17 */
18 p = convert_exp(exp_sz , convert_sz);
19 printf("%s\n",convert_sz);
20 return 0;
21 }
本文章為轉載內容，我們尊重原作者對文章享有的著作權。如有內容錯誤或侵權問題，歡迎原作者聯繫我們進行內容更正或刪除文章。
