郁闷的C小加（一）

描述

我们熟悉的表达式如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 = http://www.mamicode.com/x;>

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;}

NYOJ257郁闷的C小加（一）