郁悶的C小加(一)
時間限制: 1000 ms | 記憶體限制: 65535 KB 難度: 3
- 描述
- 我們熟悉的表達式如a+b、a+b*(c+d)等都屬于中綴表達式。中綴表達式就是(對于雙目運算符來說)操作符在兩個操作數中間:num1 operand num2。同理,字尾表達式就是操作符在兩個操作數之後:num1 num2 operand。ACM隊的“C小加”正在郁悶怎樣把一個中綴表達式轉換為字尾表達式,現在請你設計一個程式,幫助C小加把中綴表達式轉換成字尾表達式。為簡化問題,操作數均為個位數,操作符隻有+-*/ 和小括号。
- 輸入
-
第一行輸入T,表示有T組測試資料(T<10)。
每組測試資料隻有一行,是一個長度不超過1000的字元串,表示這個表達式。這個表達式裡隻包含+-*/與小括号這幾種符号。其中小括号可以嵌套使用。資料保證輸入的操作數中不會出現負數。并且輸入資料不會出現不比對現象。
輸出 - 每組輸出都單獨成行,輸出轉換的字尾表達式。 樣例輸入
-
2 1+2 (1+2)*3+4*5
樣例輸出 -
12+ 12+3*45*+
-
此題與中綴變字尾類似:具體思路可檢視http://blog.csdn.net/java_oracle_c/article/details/41986941
-
AC代碼:# include <stdio.h> # include <stdlib.h> # include <string.h> # define False 0 # define True 1
-
typedef struct node { char data; struct node *next; }LinkStackNode, *LinkStack;
-
int InitStack(LinkStack *S) //初始化棧 { (*S) = (LinkStack)malloc(sizeof(LinkStackNode)); (*S)->next = NULL; if ((*S) != NULL) return True; else return False; }
-
int Push(LinkStack S, char x) //進棧 { LinkStack temp; temp = (LinkStack)malloc(sizeof(LinkStackNode)); if (temp == NULL) return False; temp->data = x; temp->next = S->next; S->next = temp; return True; }
-
int Pop(LinkStack S) //出棧 { LinkStack temp; temp = S->next; if (temp == NULL) return False; S->next = temp->next; free(temp); return True; } int top(LinkStack S) { char e; e = S->next->data; return e; }
-
//************************************************************************* int cmp(char ch) { switch(ch) { case'+': case'-':return 1; case'*': case'/':return 2; default:return 0; } } void fun(char *a, char *b,LinkStack s) { Push(s,'#'); int i = 0,j = 0; while (i < strlen(a)) { if (a[i] == '(') { Push(s,a[i]); i++; } else if (a[i] == ')') { while (top(s) != '(') { b[j] = top(s); j++; Pop(s); } Pop(s); i++; } else if (a[i] == '+' || a[i] == '-' || a[i] == '*' || a[i] == '/') { while (cmp(top(s)) >= cmp(a[i])) { b[j] = top(s); j++; Pop(s); } Push(s,a[i]); i++; } else { while ('0' <= a[i] &&a[i] <= '9' ||a[i] == '.') { b[j] = a[i]; i++;j++; } } } while (top(s) != '#') { b[j] = top(s); j++; Pop(s); }
-
} int main(void) { int n,i; char a[1001],b[2002]; LinkStack S; scanf("%d", &n); while (n--) { memset(b,'a',sizeof(b)); InitStack(&S); scanf("%s", a); fun(a,b,S); i = 0; while (b[i] != 'a') { printf("%c",b[i]); i++; } printf("\n"); } return 0; }
-