2011-09-04 19:08:18Morris
d285. 727 Postfix Expression
d285. 727 Postfix Expression
/**********************************************************************************/
/* Problem: d285 " 727 Postfix Expression " from UVA727 */
/* Language: C */
/* Result: AC (0ms, 246KB) on ZeroJudge */
/* Author: morris1028 at 2011-09-04 15:40:08 */
/**********************************************************************************/
#include<stdio.h>
int Priority(char c) {
switch(c) {
case '(':return 1;
case ')':return 2;
case '+':return 3;
case '-':return 3;
case '*':return 4;
case '/':return 4;
case '%':return 4;
}
}
int change(char *A) {
int i, j;
int Ans[1000], Sign[1000], AIdx = -1, tmp, g;
int Stack[1000], SIdx = -1;
for(i = 0, tmp = 0, g = 0; A[i]; i++) {
if(A[i] >= '0' && A[i] <= '9')
tmp = tmp*10 + A[i]-'0', g = 1;
else {
if(g)
Ans[++AIdx] = tmp, Sign[AIdx] = 0, tmp = 0, g = 0;
Stack[++SIdx] = A[i];
if(A[i] == ')') {
SIdx--;
while(SIdx >= 0 && Stack[SIdx] != '(')
Ans[++AIdx] = Stack[SIdx], Sign[AIdx] = 1, SIdx--;
SIdx--;
}
else
while(SIdx >= 1 && Priority(Stack[SIdx-1]) >= Priority(Stack[SIdx]) && Stack[SIdx] != '(')
Ans[++AIdx] = Stack[SIdx-1], Sign[AIdx] = 1, Stack[SIdx-1] = Stack[SIdx], SIdx--;
}
}
if(g)
Ans[++AIdx] = tmp, Sign[AIdx] = 0, tmp = 0, g = 0;
while(SIdx >= 0)
Ans[++AIdx] = Stack[SIdx], Sign[AIdx] = 1, SIdx--;
for(i = 0; i <= AIdx; i++)
if(Sign[i] == 1)
printf("%c", Ans[i]);
else
printf("%d", Ans[i]);
puts("");
}
main() {
int t, C = 0;
char s[1000], *A = s, tmp[3];
scanf("%d", &t), getchar(), gets(tmp);
while(t--) {
A = s;
while(gets(tmp)) {
if(tmp[0] == '\0') break;
*A++ = tmp[0];
}
*A++ = '\0';
change(s);
if(t) puts("");
}
return 0;
}
內容 ：
根據下列的規定寫一個程式將中置運算式改成後置運算式。
1. 輸入的中置運算式每行一個字元，最多50行。例如，(3+2)*5 將以下列形式出現：
(
3
+
2
)
*
5
1. 本程式僅處理 +, -, *, / 等二元運算子。
2. 運算元為一位數數字。
3. * 和 / 運算子優先順序最高。+ 和 – 運算子則為最低。相同優先順序的運算子則由左至右運算。括號則是用來改變優先順序的群組符號。
4. 每筆測試資料均為合法的運算式。
輸入說明 ：
輸入檔第一行會有一個數字表示測試資料的筆數。接下來會有好幾個運算式，每個運算式之前會有一個空行。
輸出說明 ：
每個後置運算式輸出成一行。每個運算式之間要有一個空行。
範例輸入 ：
2 (3+2)*53+2
範例輸出 ：
32+5*32+
提示 ：
出處 ：
/**********************************************************************************/
/* Problem: d285 " 727 Postfix Expression " from UVA727 */
/* Language: C */
/* Result: AC (0ms, 246KB) on ZeroJudge */
/* Author: morris1028 at 2011-09-04 15:40:08 */
/**********************************************************************************/
#include<stdio.h>
int Priority(char c) {
switch(c) {
case '(':return 1;
case ')':return 2;
case '+':return 3;
case '-':return 3;
case '*':return 4;
case '/':return 4;
case '%':return 4;
}
}
int change(char *A) {
int i, j;
int Ans[1000], Sign[1000], AIdx = -1, tmp, g;
int Stack[1000], SIdx = -1;
for(i = 0, tmp = 0, g = 0; A[i]; i++) {
if(A[i] >= '0' && A[i] <= '9')
tmp = tmp*10 + A[i]-'0', g = 1;
else {
if(g)
Ans[++AIdx] = tmp, Sign[AIdx] = 0, tmp = 0, g = 0;
Stack[++SIdx] = A[i];
if(A[i] == ')') {
SIdx--;
while(SIdx >= 0 && Stack[SIdx] != '(')
Ans[++AIdx] = Stack[SIdx], Sign[AIdx] = 1, SIdx--;
SIdx--;
}
else
while(SIdx >= 1 && Priority(Stack[SIdx-1]) >= Priority(Stack[SIdx]) && Stack[SIdx] != '(')
Ans[++AIdx] = Stack[SIdx-1], Sign[AIdx] = 1, Stack[SIdx-1] = Stack[SIdx], SIdx--;
}
}
if(g)
Ans[++AIdx] = tmp, Sign[AIdx] = 0, tmp = 0, g = 0;
while(SIdx >= 0)
Ans[++AIdx] = Stack[SIdx], Sign[AIdx] = 1, SIdx--;
for(i = 0; i <= AIdx; i++)
if(Sign[i] == 1)
printf("%c", Ans[i]);
else
printf("%d", Ans[i]);
puts("");
}
main() {
int t, C = 0;
char s[1000], *A = s, tmp[3];
scanf("%d", &t), getchar(), gets(tmp);
while(t--) {
A = s;
while(gets(tmp)) {
if(tmp[0] == '\0') break;
*A++ = tmp[0];
}
*A++ = '\0';
change(s);
if(t) puts("");
}
return 0;
}