逆波兰式处理四则混合运算

 

　逆波兰式也叫后缀表达式(将运算符写在操作数之后)

　　如：我们平时写a+b，这是中缀表达式，写成后缀表达式就是：ab+

　　(a+b)*c-(a+b)/e的后缀表达式为：

　　(a+b)*c-(a+b)/e

　　→((a+b)*c)((a+b)/e)-

　　→((a+b)c*)((a+b)e/)-

　　→(ab+c*)(ab+e/)-

　　→ab+c*ab+e/-

下面给出一个逆波兰式四则混合运算的例子

#include <stdio.h>
#include <stdlib.h>
#define Max 100

  int exp[Max];char demo2[Max]={0}; /*定义全局变量,减少函数参数传递,exp[]为存储逆波兰式,
                                           demo[]为存储符号查标志*/

void trans(){ /*trans()转化为逆波兰式函数*/
  char str[Max];
    char demo[Max];
    char stack[Max];
    
    char ch,flag; /*ch存储字符，flag存储标志*/
    int staus = 0;
    int i = 0,j = 0,t,top = 0;
    do{ /*读取字符*/
        i++;
        scanf("%c",&demo[i]);
    } while (demo[i] != '=' && i<Max);
        i=0;
    do{ /*转化为数字*/
        j++;
        if (demo[j] >= '0' && demo[j] <= '9') {
            if (staus == 0) {
                i++;
                str[i] = demo[j] - '0';
                staus = 1;
        demo[i] = 0;
      }
            else if (staus == 1){
                str[i] = str[i] * 10 + demo[j] -'0';
                staus = 1;
                demo[i] = 0;
            }
     }
        else if (demo[j] == '(' || demo[j] == ')' || demo[j] == '+' || demo[j] == '-' || demo[j] == '*' || demo[j] == '/')
        {
            i++;
            str[i] = demo[j];
            demo[i] = 1;
            staus = 0;
     }
    } while (demo[j] != '=' && i<Max);
    
    str[i+1]=demo[j] ;
    demo[i+1] = 1;

    t = 0;i = 0;

    ch = str[i];
    flag = demo[i];i++;
    
    while (ch != '=' || flag != 1) { /*运用栈的思想将demo[]中数转化为逆波兰式存储在exp[]中，demo[]再作为符号标志*/
        if (ch == '(' && flag == 1)
        {
            top++; stack[top] = ch;
        }
        else if (ch == ')' && flag == 1)
        {
            while (stack[top] != '(')
         {
             exp[t] = stack[top];
             demo2[t] = 1;
             top--;
             t++;
         }
            top--;
        }
        else if ((ch == '+' || ch == '-') && flag == 1)
        {
            while (top != 0 && stack[top] != '(')
            {
                exp[t] = stack[top];
                demo2[t] = 1;
                top-- ;
                t++ ;
            }
            top++ ;
            stack[top] = ch;
        }
        else if ((ch == '*' || ch == '/') && flag == 1)
        {
            while (stack[top] == '*' || stack[top] == '/')
            {
                exp[t] = stack[top];
                demo2[t] = 1;
                top--;
                t++;
            }
            top++;
            stack[top]=ch;
        }
        else {
            exp[t] = ch;
            t++;
     }
        ch = str[i];
        flag = demo[i];i++;

    }
    
    
    while (top != 0)
    {
        exp[t] = stack[top];
        demo2[t] = 1;
        t++;
        top--; /*清空栈，并保存数据*/
    }
    
    
    exp[t] = '=';
    demo2[t] = 1;
    for (j=1;j<=t ; j++) { /*输出逆波兰式*/
    if (demo2[j] == 1)
    {
            printf("%3c",exp[j]);
    }
        else printf("%3d",exp[j]);
    }
    printf("\n");
    for (j=1;j<=t ; j++) { /*检测符号标志*/
    printf("%3d",demo2[j]);
    }
    printf("\n");
    
}


void compvalue(){ /*compvalue()计算函数*/
  int stack[Max],d;
  char c,f; /*ch存储字符，flag存储标志*/
  int i=0,t=0,top=0;
  c = exp[t];f = demo2[t];t++;
  while (c!='=' || f != 1){ /*计算主循环*/
    c;
    if ((c == '+' || c == '-' || c == '*' || c == '/') && f == 1)
     {
         switch (c){
        case '+':stack[top-1] = stack[top-1]+stack[top];break;
        case '-':stack[top-1] = stack[top-1]-stack[top];break;
        case '*':stack[top-1] = stack[top-1]*stack[top];break;
        case '/':
            if (stack[top]!=0) stack[top-1] = stack[top-1]/stack[top];
          else
            printf("worng div!");
          break;
      }
      top--;
    }
     else{
      top++;
      stack[top]=c;
    }
    c=exp[t];f = demo2[t];t++; /*同步标志位*/
  }
  printf("The answer is %d\n",stack[top]);
}
     
     
int main(int argc, char *argv[])
{
  trans();
  compvalue();
  return 0;
}