以下为表达式求值系列完整算法，借用C++语言，读者不妨对照下图表达式求值算法实例，仔细推敲。
1 /* 2 DATA:2015 1 30 3 From:13420228 4 */ 5 //测试数据： 6 // 4 7 // (0!+1)*2^(3!+4) - (5! - 67 - (8+9)) 8 // (1+2)*3+4*5 9 // 1.000 + 2 / 4 10 // ((1+2)*5+1)/(4^2)*3 11 #include <iostream> 12 #include <cstdlib> 13 #include <cstring> 14 #include <stack> 15 #include <cmath> 16 using namespace std; 17 #define N_OPTR 9 //运算符总数 18 typedef enum { ADD, SUB, MUL, DIV, POW, FAC, L_P, R_P, EOE } Operator; //运算符集合 19 //加、减、乘、除、乘方、阶乘、左括号、右括号、起始符与终止符 20 const char pri[N_OPTR][N_OPTR] = { //运算符优先等级 [栈顶] [当前] 21 /* |-------------------- 当 前 运 算 符 --------------------| */ 22 /* + - * / ^ ! ( ) */ 23 /* -- + */ '>', '>', '<', '<', '<', '<', '<', '>', '>', 24 /* | - */ '>', '>', '<', '<', '<', '<', '<', '>', '>', 25 /* 栈 * */ '>', '>', '>', '>', '<', '<', '<', '>', '>', 26 /* 顶 / */ '>', '>', '>', '>', '<', '<', '<', '>', '>', 27 /* 运 ^ */ '>', '>', '>', '>', '>', '<', '<', '>', '>', 28 /* 算 ! */ '>', '>', '>', '>', '>', '>', ' ', '>', '>', 29 /* 符 ( */ '<', '<', '<', '<', '<', '<', '<', '=', ' ', 30 /* | ) */ ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', 31 /* -- */ '<', '<', '<', '<', '<', '<', '<', ' ', '=' 32 }; 33 34 Operator optr2rank ( char op ) { //由运算符转译出编号 35 switch ( op ) { 36 case '+' : return ADD; //加 37 case '-' : return SUB; //减 38 case '*' : return MUL; //乘 39 case '/' : return DIV; //除 40 case '^' : return POW; //乘方 41 case '!' : return FAC; //阶乘 42 case '(' : return L_P; //左括号 43 case ')' : return R_P; //右括号 44 case ' ': return EOE; //起始符与终止符 45 default : exit ( -1 ); //未知运算符 46 } 47 } 48 char orderBetween ( char op1, char op2 ) //比较两个运算符之间的优先级 49 { return pri[optr2rank ( op1 ) ][optr2rank ( op2 ) ]; } 50 51 char* removeSpace ( char* s ) { //剔除s[]中的白空格 52 char* p = s, *q = s; 53 while ( true ) { 54 while ( isspace ( *q ) ) q++; 55 if ( ' ' == *q ) { *p = ' '; return s; } 56 *p++ = *q++; 57 } 58 } 59 60 void readNumber ( char*& p, stack<float>& stk ) { //将起始于p的子串解析为数值，并存入操作数栈 61 stk.push ( ( float ) ( *p - '0' ) ); //当前数位对应的数值进栈 62 while ( isdigit ( * ( ++p ) ) ){ //只要后续还有紧邻的数字（即多位整数的情况），则 63 float temp=stk.top() * 10 + ( *p - '0' );stk.pop();stk.push (temp );//弹出原操作数并追加新数位后，新数值重新入栈 64 } 65 if ( '.' != *p ) return; //此后非小数点，则意味着当前操作数解析完成 66 float fraction = 1; //否则，意味着还有小数部分 67 while ( isdigit ( * ( ++p ) ) ) {//逐位加入 68 float temp=stk.top() + ( *p - '0' ) * ( fraction /= 10 ); 69 stk.pop(); 70 stk.push (temp); //小数部分 71 } 72 } 73 74 __int64 facI ( int n ) { __int64 f = 1; while ( n > 1 ) f *= n--; return f; } //阶乘运算（迭代版） 75 76 void append ( char*& rpn, float opnd ) { //将操作数接至RPN末尾 针对浮点数和字符，分删重轲一个接口 77 int n = strlen ( rpn ); //RPN当前长度（以' '结尾，长度n + 1） 78 char buf[64]; 79 if ( opnd != ( float ) ( int ) opnd ) sprintf ( buf, "%.2f ", opnd ); //浮点格式，或 80 else sprintf ( buf, "%d ", ( int ) opnd ); //整数格式 81 rpn = ( char* ) realloc ( rpn, sizeof ( char ) * ( n + strlen ( buf ) + 1 ) ); //扩展空间 82 strcat ( rpn, buf ); //RPN加长 83 } 84 void append ( char*& rpn, char optr ) { //将运算符接至RPN末尾 85 int n = strlen ( rpn ); //RPN当前长度（以' '结尾，长度n + 1） 86 rpn = ( char* ) realloc ( rpn, sizeof ( char ) * ( n + 3 ) ); //扩展空间 87 sprintf ( rpn + n, "%c ", optr ); rpn[n + 2] = ' '; //接入指定的运算符 88 } 89 90 float calcu ( float a, char op, float b ) { //执行二元运算 91 switch ( op ) { 92 case '+' : return a + b; 93 case '-' : return a - b; 94 case '*' : return a * b; 95 case '/' : if ( 0==b ) exit ( -1 ); return a/b; //注意：如此判浮点数为零可能不安全 96 case '^' : return pow ( a, b ); 97 default : exit ( -1 ); 98 } 99 } 100 float calcu ( char op, float b ) { //执行一元运算 101 switch ( op ) { 102 case '!' : return ( float ) facI ( ( int ) b ); //目前仅有阶乘，可照此方式添加 103 default : exit ( -1 ); 104 } 105 } 106 107 void print(stack<float> opndStk){ 108 printf("opndStk: "); 109 while(!opndStk.empty()){ 110 printf("%.3f ",opndStk.top()); 111 opndStk.pop(); 112 } 113 } 114 void print(stack<char> optrStk){ 115 printf("optrStk: "); 116 while(!optrStk.empty()){ 117 printf("%c ",optrStk.top()); 118 optrStk.pop(); 119 } 120 } 121 void displayProgress ( char* expr, char* pCh, stack<float>& opndStk, stack<char>& optrStk, char* rpn ) {// * 显示表达式处理进展 122 system ( "cls" ); 123 printf ( " expr:" ); 124 for ( char* p = expr; ' ' != *p; p++ ) printf ( " %c", *p ); printf ( " $ expr:" ); 125 for ( char* p = expr; p < pCh; p++ ) printf ( " " ); 126 if ( ' ' != * ( pCh - 1 ) ) 127 { for ( char* p = pCh; ' ' != *p; p++ ) printf ( " %c", *p ); printf ( " $" ); } 128 printf ( " expr:" ); 129 for ( char* p = expr; p < pCh; p++ ) printf ( "--" ); printf ( " ^ " ); 130 print ( optrStk ); printf ( " " ); 131 print ( opndStk ); printf ( " " ); 132 printf ( "RPN: %s ", rpn ); //输出RPN 133 getchar(); 134 } 135 float evaluate ( char* S, char*& RPN ) { //对（已剔除白空格的）表达式S求值，并转换为逆波兰式RPN 136 stack<float> opnd; stack<char> optr; //运算数栈、运算符栈 /*DSA*/任何时刻，其中每对相邻元素之间均大小一致 137 /*DSA*/ char* expr = S; 138 optr.push ( ' ' ); //尾哨兵' '也作为头哨兵首先入栈 139 while ( !optr.empty() ) { //在运算符栈非空之前，逐个处理表达式中各字符 140 if ( isdigit ( *S ) ) { //若当前字符为操作数，则 141 readNumber ( S, opnd ); append ( RPN, opnd.top() ); //读入操作数，并将其接至RPN末尾 142 } else //若当前字符为运算符，则 143 switch ( orderBetween ( optr.top(), *S ) ) { //视其与栈顶运算符之间优先级高低分别处理 144 case '<': //栈顶运算符优先级更低时 145 optr.push ( *S ); S++; //计算推迟，当前运算符进栈 146 break; 147 case '=': //优先级相等（当前运算符为右括号或者尾部哨兵' '）时 148 optr.pop(); S++; //脱括号并接收下一个字符 149 break; 150 case '>': { //栈顶运算符优先级更高时，可实施相应的计算，并将结果重新入栈 151 char op = optr.top(); optr.pop();append ( RPN, op ); //栈顶运算符出栈并续接至RPN末尾 152 if ( '!' == op ) { //若属于一元运算符 153 float pOpnd = opnd.top();opnd.pop(); //只需取出一个操作数，并 154 opnd.push ( calcu ( op, pOpnd ) ); //实施一元计算，结果入栈 155 } else { //对于其它（二元）运算符 156 float pOpnd2 = opnd.top();opnd.pop(); 157 float pOpnd1 = opnd.top();opnd.pop(); //取出后、前操作数 /*DSA*/提问：可否省去两个临时变量？ 158 opnd.push ( calcu ( pOpnd1, op, pOpnd2 ) ); //实施二元计算，结果入栈 159 } 160 break; 161 } 162 default : exit ( -1 ); //逢语法错误，不做处理直接退出 163 }//switch 164 displayProgress ( expr, S, opnd, optr, RPN ); 165 }//while 166 float temp=opnd.top();opnd.pop(); 167 return temp; //弹出并返回最后的计算结果 168 } 169 int main ( int argc, char* argv[] ) { 170 //freopen("input.txt","r",stdin); 171 int n; 172 printf("||====================================================|| "); 173 printf("||******************表达式求值************************|| "); 174 printf("||***支持加、减、乘、除、乘方、阶乘、左括号、右括号***|| "); 175 printf("||====================================================|| "); 176 177 printf ( " please scanf the number of evaluate: " ); 178 scanf("%d",&n); 179 getchar();//处理第一行末的' ' 180 while(n--) 181 { 182 char str[100]; 183 system ( "cls" ); 184 printf ( " please scanf the evaluate: " ); 185 gets(str);//表达式求值（入口） 186 printf ( " Press [Enter] key to evaluate: [%s] ", str );getchar(); 187 char* rpn = ( char* ) malloc ( sizeof ( char ) * 1 ); rpn[0] = ' '; //逆波兰表达式 188 float value = evaluate ( removeSpace ( str ), rpn ); //求值 189 printf ( "EXPR : %s ", str ); //输出原表达式 190 printf ( "RPN : [ %s] ", rpn ); //输出RPN 191 printf ( "Value = %.3f = %d ", value, ( int ) value ); //输出表达式的值 192 free ( rpn ); rpn = NULL; 193 getchar(); 194 } 195 return 0; 196 }
显然，对以上算法稍加修改，即可得出：
1475：表达式的计算1：
1 // 3+2+1 2 // 3-2-1 3 // 1+2*3 4 // 0 5 6 #include <iostream> 7 #include <cstdlib> 8 #include <cstring> 9 #include <stack> 10 #include <cmath> 11 using namespace std; 12 #define N_OPTR 9 //运算符总数 13 typedef enum { ADD, SUB, MUL, DIV, POW, FAC, L_P, R_P, EOE } Operator; //运算符集合 14 //加、减、乘、除、乘方、阶乘、左括号、右括号、起始符与终止符 15 const char pri[N_OPTR][N_OPTR] = { //运算符优先等级 [栈顶] [当前] 16 /* |-------------------- 当 前 运 算 符 --------------------| */ 17 /* + - * / ^ ! ( ) */ 18 /* -- + */ '>', '>', '<', '<', '<', '<', '<', '>', '>', 19 /* | - */ '>', '>', '<', '<', '<', '<', '<', '>', '>', 20 /* 栈 * */ '>', '>', '>', '>', '<', '<', '<', '>', '>', 21 /* 顶 / */ '>', '>', '>', '>', '<', '<', '<', '>', '>', 22 /* 运 ^ */ '>', '>', '>', '>', '>', '<', '<', '>', '>', 23 /* 算 ! */ '>', '>', '>', '>', '>', '>', ' ', '>', '>', 24 /* 符 ( */ '<', '<', '<', '<', '<', '<', '<', '=', ' ', 25 /* | ) */ ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', 26 /* -- */ '<', '<', '<', '<', '<', '<', '<', ' ', '=' 27 }; 28 29 void readNumber ( char*& p, stack<float>& stk ) { //将起始于p的子串解析为数值，并存入操作数栈 30 stk.push ( ( float ) ( *p - '0' ) ); //当前数位对应的数值进栈 31 while ( isdigit ( * ( ++p ) ) ){ //只要后续还有紧邻的数字（即多位整数的情况），则 32 float temp=stk.top() * 10 + ( *p - '0' );stk.pop();stk.push (temp );//弹出原操作数并追加新数位后，新数值重新入栈 33 } 34 if ( '.' != *p ) return; //此后非小数点，则意味着当前操作数解析完成 35 float fraction = 1; //否则，意味着还有小数部分 36 while ( isdigit ( * ( ++p ) ) ) {//逐位加入 37 float temp=stk.top() + ( *p - '0' ) * ( fraction /= 10 ); 38 stk.pop(); 39 stk.push (temp); //小数部分 40 } 41 } 42 43 void append ( char*& rpn, float opnd ) { //将操作数接至RPN末尾 44 int n = strlen ( rpn ); //RPN当前长度（以' '结尾，长度n + 1） 45 char buf[64]; 46 if ( opnd != ( float ) ( int ) opnd ) sprintf ( buf, "%.2f ", opnd ); //浮点格式，或 47 else sprintf ( buf, "%d ", ( int ) opnd ); //整数格式 48 rpn = ( char* ) realloc ( rpn, sizeof ( char ) * ( n + strlen ( buf ) + 1 ) ); //扩展空间 49 strcat ( rpn, buf ); //RPN加长 50 } 51 52 void append ( char*& rpn, char optr ) { //将运算符接至RPN末尾 53 int n = strlen ( rpn ); //RPN当前长度（以' '结尾，长度n + 1） 54 rpn = ( char* ) realloc ( rpn, sizeof ( char ) * ( n + 3 ) ); //扩展空间 55 sprintf ( rpn + n, "%c", optr ); rpn[n + 2] = ' '; //接入指定的运算符 56 } 57 58 Operator optr2rank ( char op ) { //由运算符转译出编号 59 switch ( op ) { 60 case '+' : return ADD; //加 61 case '-' : return SUB; //减 62 case '*' : return MUL; //乘 63 case '/' : return DIV; //除 64 case '^' : return POW; //乘方 65 case '!' : return FAC; //阶乘 66 case '(' : return L_P; //左括号 67 case ')' : return R_P; //右括号 68 case ' ': return EOE; //起始符与终止符 69 default : exit ( -1 ); //未知运算符 70 } 71 } 72 73 char orderBetween ( char op1, char op2 ) //比较两个运算符之间的优先级 74 { return pri[optr2rank ( op1 ) ][optr2rank ( op2 ) ]; } 75 76 77 __int64 facI ( int n ) { __int64 f = 1; while ( n > 1 ) f *= n--; return f; } //阶乘运算（迭代版） 78 79 float calcu ( float a, char op, float b ) { //执行二元运算 80 switch ( op ) { 81 case '+' : return a + b; 82 case '-' : return a - b; 83 case '*' : return a * b; 84 case '/' : if ( 0==b ) exit ( -1 ); return a/b; //注意：如此判浮点数为零可能不安全 85 case '^' : return pow ( a, b ); 86 default : exit ( -1 ); 87 } 88 } 89 float calcu ( char op, float b ) { //执行一元运算 90 switch ( op ) { 91 case '!' : return ( float ) facI ( ( int ) b ); //目前仅有阶乘，可照此方式添加 92 default : exit ( -1 ); 93 } 94 } 95 96 float evaluate ( char* S, char*& RPN ) { //对（已剔除白空格的）表达式S求值，并转换为逆波兰式RPN 97 stack<float> opnd; stack<char> optr; //运算数栈、运算符栈 /*DSA*/任何时刻，其中每对相邻元素之间均大小一致 98 /*DSA*/ char* expr = S; 99 optr.push ( ' ' ); //尾哨兵' '也作为头哨兵首先入栈 100 while ( !optr.empty() ) { //在运算符栈非空之前，逐个处理表达式中各字符 101 if ( isdigit ( *S ) ) { //若当前字符为操作数，则 102 readNumber ( S, opnd ); append ( RPN, opnd.top() ); //读入操作数，并将其接至RPN末尾 103 } else //若当前字符为运算符，则 104 switch ( orderBetween ( optr.top(), *S ) ) { //视其与栈顶运算符之间优先级高低分别处理 105 case '<': //栈顶运算符优先级更低时 106 optr.push ( *S ); S++; //计算推迟，当前运算符进栈 107 break; 108 case '=': //优先级相等（当前运算符为右括号或者尾部哨兵' '）时 109 optr.pop(); S++; //脱括号并接收下一个字符 110 break; 111 case '>': { //栈顶运算符优先级更高时，可实施相应的计算，并将结果重新入栈 112 char op = optr.top(); optr.pop();append ( RPN, op ); //栈顶运算符出栈并续接至RPN末尾 113 if ( '!' == op ) { //若属于一元运算符 114 float pOpnd = opnd.top();opnd.pop(); //只需取出一个操作数，并 115 opnd.push ( calcu ( op, pOpnd ) ); //实施一元计算，结果入栈 116 } else { //对于其它（二元）运算符 117 float pOpnd2 = opnd.top();opnd.pop(); 118 float pOpnd1 = opnd.top();opnd.pop(); //取出后、前操作数 /*DSA*/提问：可否省去两个临时变量？ 119 opnd.push ( calcu ( pOpnd1, op, pOpnd2 ) ); //实施二元计算，结果入栈 120 } 121 break; 122 } 123 default : exit ( -1 ); //逢语法错误，不做处理直接退出 124 }//switch 125 /*DSA*///displayProgress ( expr, S, opnd, optr, RPN ); 126 }//while 127 float temp=opnd.top();opnd.pop(); 128 return temp; //弹出并返回最后的计算结果 129 } 130 char* removeSpace ( char* s ) { //剔除s[]中的白空格 131 char* p = s, *q = s; 132 while ( true ) { 133 while ( isspace ( *q ) ) q++; 134 if ( ' ' == *q ) { *p = ' '; return s; } 135 *p++ = *q++; 136 } 137 } 138 int main ( int argc, char* argv[] ) { //表达式求值（入口） 139 // freopen("input.txt","r",stdin); 140 while(true) 141 { 142 char str[100]; 143 gets(str); 144 if(str[0]=='0') break; 145 //for ( int i = 0; i < strlen(str); i++ ) { //逐一处理各命令行参数（表达式） 146 ///*DSA*/system ( "cls" ); // 147 //printf ( " Press any key to evaluate: [%s] ", str ); 148 char* rpn = ( char* ) malloc ( sizeof ( char ) * 1 ); rpn[0] = ' '; //逆波兰表达式 149 float value = evaluate ( removeSpace ( str ), rpn ); //求值 150 ///*DSA*/printf ( "EXPR : %s ", str ); //输出原表达式 151 ///*DSA*/printf ( "%s ", rpn ); //输出RPN 152 /*DSA*/printf ( "%d ",( int ) value ); //输出表达式的值 153 free ( rpn ); rpn = NULL; 154 } 155 return 0; 156 }
1477：中缀转换成后缀：
1 //测试用例： 2 // 2 3 // 1+2 4 // (1+2)*3+4*5 5 6 #include <iostream> 7 #include <cstdlib> 8 #include <cstring> 9 #include <stack> 10 #include <cmath> 11 using namespace std; 12 #define N_OPTR 9 //运算符总数 13 typedef enum { ADD, SUB, MUL, DIV, POW, FAC, L_P, R_P, EOE } Operator; //运算符集合 14 //加、减、乘、除、乘方、阶乘、左括号、右括号、起始符与终止符 15 const char pri[N_OPTR][N_OPTR] = { //运算符优先等级 [栈顶] [当前] 16 /* |-------------------- 当 前 运 算 符 --------------------| */ 17 /* + - * / ^ ! ( ) */ 18 /* -- + */ '>', '>', '<', '<', '<', '<', '<', '>', '>', 19 /* | - */ '>', '>', '<', '<', '<', '<', '<', '>', '>', 20 /* 栈 * */ '>', '>', '>', '>', '<', '<', '<', '>', '>', 21 /* 顶 / */ '>', '>', '>', '>', '<', '<', '<', '>', '>', 22 /* 运 ^ */ '>', '>', '>', '>', '>', '<', '<', '>', '>', 23 /* 算 ! */ '>', '>', '>', '>', '>', '>', ' ', '>', '>', 24 /* 符 ( */ '<', '<', '<', '<', '<', '<', '<', '=', ' ', 25 /* | ) */ ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', 26 /* -- */ '<', '<', '<', '<', '<', '<', '<', ' ', '=' 27 }; 28 29 void readNumber ( char*& p, stack<float>& stk ) { //将起始于p的子串解析为数值，并存入操作数栈 30 stk.push ( ( float ) ( *p - '0' ) ); //当前数位对应的数值进栈 31 while ( isdigit ( * ( ++p ) ) ){ //只要后续还有紧邻的数字（即多位整数的情况），则 32 float temp=stk.top() * 10 + ( *p - '0' );stk.pop();stk.push (temp );//弹出原操作数并追加新数位后，新数值重新入栈 33 } 34 if ( '.' != *p ) return; //此后非小数点，则意味着当前操作数解析完成 35 float fraction = 1; //否则，意味着还有小数部分 36 while ( isdigit ( * ( ++p ) ) ) {//逐位加入 37 float temp=stk.top() + ( *p - '0' ) * ( fraction /= 10 ); 38 stk.pop(); 39 stk.push (temp); //小数部分 40 } 41 } 42 43 void append ( char*& rpn, float opnd ) { //将操作数接至RPN末尾 44 int n = strlen ( rpn ); //RPN当前长度（以' '结尾，长度n + 1） 45 char buf[64]; 46 if ( opnd != ( float ) ( int ) opnd ) sprintf ( buf, "%.2f ", opnd ); //浮点格式，或 47 else sprintf ( buf, "%d ", ( int ) opnd ); //整数格式 48 rpn = ( char* ) realloc ( rpn, sizeof ( char ) * ( n + strlen ( buf ) + 1 ) ); //扩展空间 49 strcat ( rpn, buf ); //RPN加长 50 } 51 void append ( char*& rpn, char optr ) { //将运算符接至RPN末尾 52 int n = strlen ( rpn ); //RPN当前长度（以' '结尾，长度n + 1） 53 rpn = ( char* ) realloc ( rpn, sizeof ( char ) * ( n + 3 ) ); //扩展空间 54 sprintf ( rpn + n, "%c", optr ); rpn[n + 2] = ' '; //接入指定的运算符 55 } 56 57 Operator optr2rank ( char op ) { //由运算符转译出编号 58 switch ( op ) { 59 case '+' : return ADD; //加 60 case '-' : return SUB; //减 61 case '*' : return MUL; //乘 62 case '/' : return DIV; //除 63 case '^' : return POW; //乘方 64 case '!' : return FAC; //阶乘 65 case '(' : return L_P; //左括号 66 case ')' : return R_P; //右括号 67 case ' ': return EOE; //起始符与终止符 68 default : exit ( -1 ); //未知运算符 69 } 70 } 71 72 char orderBetween ( char op1, char op2 ) //比较两个运算符之间的优先级 73 { return pri[optr2rank ( op1 ) ][optr2rank ( op2 ) ]; } 74 75 76 __int64 facI ( int n ) { __int64 f = 1; while ( n > 1 ) f *= n--; return f; } //阶乘运算（迭代版） 77 78 float calcu ( float a, char op, float b ) { //执行二元运算 79 switch ( op ) { 80 case '+' : return a + b; 81 case '-' : return a - b; 82 case '*' : return a * b; 83 case '/' : if ( 0==b ) exit ( -1 ); return a/b; //注意：如此判浮点数为零可能不安全 84 case '^' : return pow ( a, b ); 85 default : exit ( -1 ); 86 } 87 } 88 float calcu ( char op, float b ) { //执行一元运算 89 switch ( op ) { 90 case '!' : return ( float ) facI ( ( int ) b ); //目前仅有阶乘，可照此方式添加 91 default : exit ( -1 ); 92 } 93 } 94 95 float evaluate ( char* S, char*& RPN ) { //对（已剔除白空格的）表达式S求值，并转换为逆波兰式RPN 96 stack<float> opnd; stack<char> optr; //运算数栈、运算符栈 /*DSA*/任何时刻，其中每对相邻元素之间均大小一致 97 /*DSA*/ char* expr = S; 98 optr.push ( ' ' ); //尾哨兵' '也作为头哨兵首先入栈 99 while ( !optr.empty() ) { //在运算符栈非空之前，逐个处理表达式中各字符 100 if ( isdigit ( *S ) ) { //若当前字符为操作数，则 101 readNumber ( S, opnd ); append ( RPN, opnd.top() ); //读入操作数，并将其接至RPN末尾 102 } else //若当前字符为运算符，则 103 switch ( orderBetween ( optr.top(), *S ) ) { //视其与栈顶运算符之间优先级高低分别处理 104 case '<': //栈顶运算符优先级更低时 105 optr.push ( *S ); S++; //计算推迟，当前运算符进栈 106 break; 107 case '=': //优先级相等（当前运算符为右括号或者尾部哨兵' '）时 108 optr.pop(); S++; //脱括号并接收下一个字符 109 break; 110 case '>': { //栈顶运算符优先级更高时，可实施相应的计算，并将结果重新入栈 111 char op = optr.top(); optr.pop();append ( RPN, op ); //栈顶运算符出栈并续接至RPN末尾 112 if ( '!' == op ) { //若属于一元运算符 113 float pOpnd = opnd.top();opnd.pop(); //只需取出一个操作数，并 114 opnd.push ( calcu ( op, pOpnd ) ); //实施一元计算，结果入栈 115 } else { //对于其它（二元）运算符 116 float pOpnd2 = opnd.top();opnd.pop(); 117 float pOpnd1 = opnd.top();opnd.pop(); //取出后、前操作数 /*DSA*/提问：可否省去两个临时变量？ 118 opnd.push ( calcu ( pOpnd1, op, pOpnd2 ) ); //实施二元计算，结果入栈 119 } 120 break; 121 } 122 default : exit ( -1 ); //逢语法错误，不做处理直接退出 123 }//switch 124 /*DSA*///displayProgress ( expr, S, opnd, optr, RPN ); 125 }//while 126 float temp=opnd.top();opnd.pop(); 127 return temp; //弹出并返回最后的计算结果 128 } 129 char* removeSpace ( char* s ) { //剔除s[]中的白空格 130 char* p = s, *q = s; 131 while ( true ) { 132 while ( isspace ( *q ) ) q++; 133 if ( ' ' == *q ) { *p = ' '; return s; } 134 *p++ = *q++; 135 } 136 } 137 138 int main ( int argc, char* argv[] ) { 139 // freopen("input.txt","r",stdin); 140 int n; 141 scanf("%d",&n); 142 getchar(); 143 while(n--) 144 { 145 char str[100]; 146 gets(str); 147 //printf ( " Press any key to evaluate: [%s] ", str ); 148 char* rpn = ( char* ) malloc ( sizeof ( char ) * 1 ); rpn[0] = ' '; //逆波兰表达式 149 float value = evaluate ( removeSpace ( str ), rpn ); //求值 150 ///*DSA*/printf ( "EXPR : %s ", str ); //输出原表达式 151 /*DSA*/printf ( "%s ", rpn ); //输出RPN 152 ///*DSA*/printf ( "Value = %.1f = %d ", value, ( int ) value ); //输出表达式的值 153 free ( rpn ); rpn = NULL; 154 } 155 return 0; 156 }
1479：表达式的计算2：
1 //测试用例 2 // 2 3 // 1.000+2/4= 4 // ((1+2)*5+1)/4= 5 #include <iostream> 6 #include <cstdlib> 7 #include <cstring> 8 #include <stack> 9 #include <cmath> 10 using namespace std; 11 #define N_OPTR 9 //运算符总数 12 typedef enum { ADD, SUB, MUL, DIV, POW, FAC, L_P, R_P, EOE } Operator; //运算符集合 13 //加、减、乘、除、乘方、阶乘、左括号、右括号、起始符与终止符 14 const char pri[N_OPTR][N_OPTR] = { //运算符优先等级 [栈顶] [当前] 15 /* |-------------------- 当 前 运 算 符 --------------------| */ 16 /* + - * / ^ ! ( ) */ 17 /* -- + */ '>', '>', '<', '<', '<', '<', '<', '>', '>', 18 /* | - */ '>', '>', '<', '<', '<', '<', '<', '>', '>', 19 /* 栈 * */ '>', '>', '>', '>', '<', '<', '<', '>', '>', 20 /* 顶 / */ '>', '>', '>', '>', '<', '<', '<', '>', '>', 21 /* 运 ^ */ '>', '>', '>', '>', '>', '<', '<', '>', '>', 22 /* 算 ! */ '>', '>', '>', '>', '>', '>', ' ', '>', '>', 23 /* 符 ( */ '<', '<', '<', '<', '<', '<', '<', '=', ' ', 24 /* | ) */ ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', 25 /* -- */ '<', '<', '<', '<', '<', '<', '<', ' ', '=' 26 }; 27 28 void readNumber ( char*& p, stack<float>& stk ) { //将起始于p的子串解析为数值，并存入操作数栈 29 stk.push ( ( float ) ( *p - '0' ) ); //当前数位对应的数值进栈 30 while ( isdigit ( * ( ++p ) ) ){ //只要后续还有紧邻的数字（即多位整数的情况），则 31 float temp=stk.top() * 10 + ( *p - '0' );stk.pop();stk.push (temp );//弹出原操作数并追加新数位后，新数值重新入栈 32 } 33 if ( '.' != *p ) return; //此后非小数点，则意味着当前操作数解析完成 34 float fraction = 1; //否则，意味着还有小数部分 35 while ( isdigit ( * ( ++p ) ) ) {//逐位加入 36 float temp=stk.top() + ( *p - '0' ) * ( fraction /= 10 ); 37 stk.pop(); 38 stk.push (temp); //小数部分 39 } 40 } 41 42 void append ( char*& rpn, float opnd ) { //将操作数接至RPN末尾 43 int n = strlen ( rpn ); //RPN当前长度（以' '结尾，长度n + 1） 44 char buf[64]; 45 if ( opnd != ( float ) ( int ) opnd ) sprintf ( buf, "%.2f ", opnd ); //浮点格式，或 46 else sprintf ( buf, "%d ", ( int ) opnd ); //整数格式 47 rpn = ( char* ) realloc ( rpn, sizeof ( char ) * ( n + strlen ( buf ) + 1 ) ); //扩展空间 48 strcat ( rpn, buf ); //RPN加长 49 } 50 void append ( char*& rpn, char optr ) { //将运算符接至RPN末尾 51 int n = strlen ( rpn ); //RPN当前长度（以' '结尾，长度n + 1） 52 rpn = ( char* ) realloc ( rpn, sizeof ( char ) * ( n + 3 ) ); //扩展空间 53 sprintf ( rpn + n, "%c", optr ); rpn[n + 2] = ' '; //接入指定的运算符 54 } 55 56 Operator optr2rank ( char op ) { //由运算符转译出编号 57 switch ( op ) { 58 case '+' : return ADD; //加 59 case '-' : return SUB; //减 60 case '*' : return MUL; //乘 61 case '/' : return DIV; //除 62 case '^' : return POW; //乘方 63 case '!' : return FAC; //阶乘 64 case '(' : return L_P; //左括号 65 case ')' : return R_P; //右括号 66 case ' ': return EOE; //起始符与终止符 67 default : exit ( -1 ); //未知运算符 68 } 69 } 70 71 char orderBetween ( char op1, char op2 ) //比较两个运算符之间的优先级 72 { return pri[optr2rank ( op1 ) ][optr2rank ( op2 ) ]; } 73 74 __int64 facI ( int n ) { __int64 f = 1; while ( n > 1 ) f *= n--; return f; } //阶乘运算（迭代版） 75 76 float calcu ( float a, char op, float b ) { //执行二元运算 77 switch ( op ) { 78 case '+' : return a + b; 79 case '-' : return a - b; 80 case '*' : return a * b; 81 case '/' : if ( 0==b ) exit ( -1 ); return a/b; //注意：如此判浮点数为零可能不安全 82 case '^' : return pow ( a, b ); 83 default : exit ( -1 ); 84 } 85 } 86 87 float calcu ( char op, float b ) { //执行一元运算 88 switch ( op ) { 89 case '!' : return ( float ) facI ( ( int ) b ); //目前仅有阶乘，可照此方式添加 90 default : exit ( -1 ); 91 } 92 } 93 94 float evaluate ( char* S, char*& RPN ) { //对（已剔除白空格的）表达式S求值，并转换为逆波兰式RPN 95 stack<float> opnd; stack<char> optr; //运算数栈、运算符栈 /*DSA*/任何时刻，其中每对相邻元素之间均大小一致 96 /*DSA*/ char* expr = S; 97 optr.push ( ' ' ); //尾哨兵' '也作为头哨兵首先入栈 98 while ( !optr.empty() ) { //在运算符栈非空之前，逐个处理表达式中各字符 99 if ( isdigit ( *S ) ) { //若当前字符为操作数，则 100 readNumber ( S, opnd ); append ( RPN, opnd.top() ); //读入操作数，并将其接至RPN末尾 101 } else //若当前字符为运算符，则 102 switch ( orderBetween ( optr.top(), *S ) ) { //视其与栈顶运算符之间优先级高低分别处理 103 case '<': //栈顶运算符优先级更低时 104 optr.push ( *S ); S++; //计算推迟，当前运算符进栈 105 break; 106 case '=': //优先级相等（当前运算符为右括号或者尾部哨兵' '）时 107 optr.pop(); S++; //脱括号并接收下一个字符 108 break; 109 case '>': { //栈顶运算符优先级更高时，可实施相应的计算，并将结果重新入栈 110 char op = optr.top(); optr.pop();append ( RPN, op ); //栈顶运算符出栈并续接至RPN末尾 111 if ( '!' == op ) { //若属于一元运算符 112 float pOpnd = opnd.top();opnd.pop(); //只需取出一个操作数，并 113 opnd.push ( calcu ( op, pOpnd ) ); //实施一元计算，结果入栈 114 } else { //对于其它（二元）运算符 115 float pOpnd2 = opnd.top();opnd.pop(); 116 float pOpnd1 = opnd.top();opnd.pop(); //取出后、前操作数 /*DSA*/提问：可否省去两个临时变量？ 117 opnd.push ( calcu ( pOpnd1, op, pOpnd2 ) ); //实施二元计算，结果入栈 118 } 119 break; 120 } 121 default : exit ( -1 ); //逢语法错误，不做处理直接退出 122 }//switch 123 /*DSA*///displayProgress ( expr, S, opnd, optr, RPN ); 124 }//while 125 float temp=opnd.top();opnd.pop(); 126 return temp; //弹出并返回最后的计算结果 127 } 128 129 char* removeSpace ( char* s ) { //剔除s[]中的白空格 130 char* p = s, *q = s; 131 while ( true ) { 132 while ( isspace ( *q ) ) q++; 133 if ( ' ' == *q ) { *p = ' '; return s; } 134 *p++ = *q++; 135 } 136 } 137 138 int main ( int argc, char* argv[] ) { //表达式求值（入口） 139 // freopen("input.txt","r",stdin); 140 int n; 141 scanf("%d",&n); 142 getchar(); 143 while(n--) 144 { 145 char str[1001]; 146 gets(str); 147 if(str[strlen(str)-1]=='=') str[strlen(str)-1]=' '; 148 //for ( int i = 0; i < strlen(str); i++ ) { //逐一处理各命令行参数（表达式） 149 ///*DSA*/system ( "cls" ); // 150 //printf ( " Press any key to evaluate: [%s] ", str ); 151 char* rpn = ( char* ) malloc ( sizeof ( char ) * 1 ); rpn[0] = ' '; //逆波兰表达式 152 float value = evaluate ( removeSpace ( str ), rpn ); //求值 153 ///*DSA*/printf ( "EXPR : %s ", str ); //输出原表达式 154 ///*DSA*/printf ( "%s ", rpn ); //输出RPN 155 /*DSA*/printf ( "%.2f ",value ); //输出表达式的值 156 free ( rpn ); rpn = NULL; 157 } 158 return 0; 159 }
附：1470：逆波兰表达式
1 // 测试用例: 2 // * - 2 3 4 3 // - 3 2 4 // - 7 7 5 // * + 11.0 12.0 + 24.0 35.0 6 #include <iostream> 7 #include <cstdlib> 8 #include <cmath> 9 using namespace std; 10 double Evaluate()//波兰（前缀）表达式递归求值算法，需要好好理解 11 { 12 char a[15];//用于存储每次递归读取的一个非空字符（串） 13 if (scanf("%s", &a) == EOF) exit(0);//处理多组数据正常结束的问题 14 switch (a[0]) 15 { 16 case '+': return Evaluate() + Evaluate(); 17 case '-': return Evaluate() - Evaluate(); 18 case '*': return Evaluate() * Evaluate(); 19 case '/': return Evaluate() / Evaluate(); 20 default: return atof(a); 21 } 22 } 23 int main(int argc, char const *argv[]) 24 { 25 //#ifndef _OJ_ //ONLINE_JUDGE 26 // freopen("input.txt", "r", stdin); 27 // freopen("output.txt", "w", stdout); 28 //#endif 29 while (1) printf("%f ",Evaluate()); 30 return 0; 31 }