3.21.c

数据结构习题及答案

◆3.21③  假设表达式由单字母变量和双目四则运
算算符构成。试写一个算法，将一个通常书写形式
且书写正确的表达式转换为逆波兰式。

实现下列函数：
char *RPExpression(char *e);
/* 返回表达式e的逆波兰式 */

Stack是一个已实现的栈。
可使用的相关类型和函数：
typedef char SElemType; // 栈Stack的元素类型
Status InitStack(Stack &s);
Status Push(Stack &s, SElemType e);
Status Pop(Stack &s, SElemType &e);
Status StackEmpty(Stack s);
SElemType Top(Stack s);
char *RPExpression(char *e)
/* 返回表达式e的逆波兰式 */
{
 char *temp,c;
 temp=(char*)malloc(strlen(e)*sizeof(char));
 int i=0;
 Stack SignStack;                          //SignStack用于存放符号
 InitStack(SignStack);

 for(;*e!='\0';e++)
 {
  if((*e!='+')&&(*e!='-')&&(*e!='*')&&(*e!='/')&&(*e!='(')&&(*e!=')'))
  {
   *(temp+i)=*e;
   i++;                                   //非符号直接写入字符数组
  }
  else
  {
   switch(*e)
   {    
    case '+':                             //运算优先级数越高越靠栈底
    case '-':while(!(StackEmpty(SignStack)) && !(Top(SignStack)=='('))
             {
              Pop(SignStack,c);
              *(temp+i)=c;
              i++;
             }
             Push(SignStack,*e);
             break;
    case '*':
    case '/':if((Top(SignStack)=='*')||(Top(SignStack)=='/'))
             {
              Pop(SignStack,c);
              *(temp+i)=c;
              i++;
              Push(SignStack,*e);
             } 
             else Push(SignStack,*e);
             break;
    case '(':Push(SignStack,*e);break;
    case ')':while(Top(SignStack)!='(')
             {
              Pop(SignStack, c);
              *(temp+i)=c;
              i++;              
             }
             Pop(SignStack, c);
             break;
   }
  }
 }
 while(!(StackEmpty(SignStack)))                 //符号全部出栈
 {
  Pop(SignStack,c);
  *(temp+i)=c;
  i++;
 }
 *(temp+i)='\0';
 return temp;

}