给定一个中缀表达式,求出该表达式的值。

要求支持“加减乘除 + - * /、取余 %、幂运算 ^、一元正负号 + -、括号 ()、数的科学表示法符号 E e”,其中含有一元操作符’+ -‘,也含有从右向左结合性的操作符’^‘,注意操作数的位数可以为多位。

直接计算中缀表达式

延迟缓冲:自左向右扫描表达式,用栈记录已扫描的部分(含已执行运算的结果)。在每一字符处,while(栈的顶部存在可优先计算的子表达式),该子表达式退栈;计算其数值计算结果进栈。当前字符进栈,转入下一字符。

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
float evaluate(char* S, char*& RPN) { //对(已剔除白空格的)表达式S求值,并转换为逆波兰式RPN
   Stack<float> opnd; Stack<char> optr; //运算数栈、运算符栈
   optr.push('\0'); //尾哨兵'\0'也作为头哨兵首先入栈
   while (!optr.empty()) { //在运算符栈非空之前,逐个处理表达式中各字符
      if (isdigit(*S)) { //若当前字符为操作数,则
         readNumber(S, opnd); append(RPN, opnd.top()); //读入操作数,并将其接至RPN末尾
      } else //若当前字符为运算符,则
         switch(orderBetween(optr.top(), *S)) { //视其与栈顶运算符之间优先级高低分别处理
            case '<': //栈顶运算符优先级更低时
               optr.push(*S); S++; //计算推迟,当前运算符进栈
               break;
            case '=': //优先级相等(当前运算符为右括号或者尾部哨兵'\0')时
               optr.pop(); S++; //脱括号并接收下一个字符
               break;
            case '>': { //栈顶运算符优先级更高时,可实施相应的计算,并将结果重新入栈
               char op = optr.pop(); append(RPN, op); //栈顶运算符出栈并续接至RPN末尾
               if ('!' == op) { //若属于一元运算符
                  float pOpnd = opnd.pop(); //只需取出一个操作数,并
                  opnd.push(calcu(op, pOpnd)); //实施一元计算,结果入栈
               } else { //对于其它(二元)运算符
                  float pOpnd2 = opnd.pop(), pOpnd1 = opnd.pop(); //取出后、前操作数
                  opnd.push(calcu(pOpnd1, op, pOpnd2)); //实施二元计算,结果入栈
              }
              break;
          }
          default : exit(-1);
         }//switch
   }//while
   return opnd.pop(); //弹出并返回最后的计算结果
}

#define N_OPTR 9 //运算符总数
typedef enum {ADD, SUB, MUL, DIV, POW, FAC, L_P, R_P, EOE} Operator; //运算符集合
//加、减、乘、除、乘方、阶乘、左括号、右括号、起始符与终止符

const char pri[N_OPTR][N_OPTR] = { //运算符优先等级 [栈顶] [当前]
/*            |-------------- 当前运算符 --------------|	*/
/*            +    -    *    /    ^    !    (    )    \0	*/
/* --  + */  '>', '>', '<', '<', '<', '<', '<', '>', '>',
/* |   - */  '>', '>', '<', '<', '<', '<', '<', '>', '>',
/* 栈  * */  '>', '>', '>', '>', '<', '<', '<', '>', '>',
/* 顶  / */  '>', '>', '>', '>', '<', '<', '<', '>', '>',
/* 运  ^ */  '>', '>', '>', '>', '>', '<', '<', '>', '>',
/* 算  ! */  '>', '>', '>', '>', '>', '>', ' ', '>', '>',
/* 符  ( */  '<', '<', '<', '<', '<', '<', '<', '=', ' ',
/* |   ) */  ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ',
/* -- \0 */  '<', '<', '<', '<', '<', '<', '<', ' ', '='
};

Operator optr2rank(char op) { //由运算符转译出编号
	switch (op) {
      case '+' : return ADD; //加
      case '-' : return SUB; //减
      case '*' : return MUL; //乘
      case '/' : return DIV; //除
      case '^' : return POW; //乘方
      case '!' : return FAC; //阶乘
      case '(' : return L_P; //左括号
      case ')' : return R_P; //右括号
      case '\0': return EOE; //起始符与终止符
      default  : exit(-1); //未知运算符
  }
}

char orderBetween(char op1, char op2) //比较两个运算符之间的优先级
{ return pri[optr2rank(op1)][optr2rank(op2)]; }

void readNumber(char*& p, Stack<float>& stk) { //将起始于p的子串解析为数值,并存入操作数栈
   stk.push((float)(*p - '0')); //当前数位对应的数值进栈
   while (isdigit(*(++p))) //只要后续还有紧邻的数字(即多位整数的情况),则
      stk.push(stk.pop() * 10 + (*p - '0')); //弹出原操作数并追加新数位后,新数值重新入栈
   if ('.' != *p) return; //此后非小数点,则意味着当前操作数解析完成
   float fraction = 1; //否则,意味着还有小数部分
   while (isdigit(*(++p))) //逐位加入
      stk.push(stk.pop() + (*p - '0')*(fraction /= 10)); //小数部分
}

float calcu(float a, char op, float b) { //执行二元运算
	switch (op) {
		case '+' : return a + b;
		case '-' : return a - b;
		case '*' : return a * b;
      case '/' : if (0==b) exit(-1); return a/b; //注意:如此判浮点数为零可能不安全
      case '^' : return pow(a, b);
      default  : exit(-1);
  }
}

float calcu(char op, float b) { //执行一元运算
	switch (op) {
      case '!' : return (float)facI((int)b); //目前仅有阶乘,可照此方式添加
      default  : exit(-1);
  }
}

void append(char*& rpn, float opnd) { //将操作数接至RPN末尾
   int n = strlen(rpn); //RPN当前长度(以'\0'结尾,长度n + 1)
   char buf[64];
   if (opnd != (float)(int)opnd) sprintf(buf, "%.2f \0", opnd); //浮点格式,或
   else                          sprintf(buf, "%d \0", (int)opnd); //整数格式
   rpn = (char*) realloc(rpn, sizeof(char) * (n + strlen(buf) + 1)); //扩展空间
   strcat(rpn, buf); //RPN加长
}

void append(char*& rpn, char optr) { //将运算符接至RPN末尾
   int n = strlen(rpn); //RPN当前长度(以'\0'结尾,长度n + 1)
   rpn = (char*) realloc(rpn, sizeof(char) * (n + 3)); //扩展空间
   sprintf(rpn + n, "%c ", optr); rpn[n + 2] = '\0'; //接入指定的运算符
}

中缀转后缀

首先介绍一个人工转换的方法,假设有一个中缀表达式a+b*c-(d+e)

  1. 首先将这个中缀表达式的所有运算加括号((a+(b*c))-(d+e))

  2. 然后将所有运算符放到括号后面,这样就变成了((a(bc)* )+ (de)+ )-

  3. 把所有括号去掉abc*+de+-,最后得出的结果就是后缀表达式

上面这个方法可以在比如做题分析的时候用人脑的时候使用,接下来介绍用程序实现将中缀转换成后缀表达式的思路

预处理中缀表达式

  1. 判断是否有不能处理的字符;

  2. 去除所有的空格;

  3. 处理一元操作符’+‘和’-‘:

    3.1 如果是在开始位置,在开始处添加”0”;

    3.2 如果是在“非数字字符”(右括号‘)’除外)之后,那么先在一元操作符前插入”(0”,然后在一个“完整的数字”或者“括号后面”添加右括号”)“;

中缀转后缀

  1. 如果是操作数,读取其所有的位,然后进入后缀表达式队列;
  2. 如果是操作符( + – * / ^ % ) 2.1 如果“操作符栈”为空,直接入栈; 2.2 如果当前操作符优先级>栈顶元素优先级,那么入栈; 2.3 如果当前操作符优先级<栈顶元素优先级,那么栈顶操作符出栈,循环执行; 2.4 如果当前操作符优先级=栈顶元素优先级,如果当前元素是右结合性,那么入栈;否则,栈顶元素出栈;循环执行。
  3. 如果是左括号’(‘,直接入栈
  4. 如果是右括号’)‘,如果栈非空,那么栈顶元素出栈,直到遇到左括号’(‘;
  5. 遍历结束中,将操作符栈中的元素依次出栈,添加到后缀表达式队列中。

参考: http://blog.csdn.net/daheiantian/article/details/6553713