首页 > 代码库 > 表达式求值算法、rpn、1470、1475、1477、1479
表达式求值算法、rpn、1470、1475、1477、1479
以下为表达式求值系列完整算法，借用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 /* + - * / ^ ! ( ) \0 */ 23 /* -- + */ ‘>‘, ‘>‘, ‘<‘, ‘<‘, ‘<‘, ‘<‘, ‘<‘, ‘>‘, ‘>‘, 24 /* | - */ ‘>‘, ‘>‘, ‘<‘, ‘<‘, ‘<‘, ‘<‘, ‘<‘, ‘>‘, ‘>‘, 25 /* 栈 * */ ‘>‘, ‘>‘, ‘>‘, ‘>‘, ‘<‘, ‘<‘, ‘<‘, ‘>‘, ‘>‘, 26 /* 顶 / */ ‘>‘, ‘>‘, ‘>‘, ‘>‘, ‘<‘, ‘<‘, ‘<‘, ‘>‘, ‘>‘, 27 /* 运 ^ */ ‘>‘, ‘>‘, ‘>‘, ‘>‘, ‘>‘, ‘<‘, ‘<‘, ‘>‘, ‘>‘, 28 /* 算 ! */ ‘>‘, ‘>‘, ‘>‘, ‘>‘, ‘>‘, ‘>‘, ‘ ‘, ‘>‘, ‘>‘, 29 /* 符 ( */ ‘<‘, ‘<‘, ‘<‘, ‘<‘, ‘<‘, ‘<‘, ‘<‘, ‘=‘, ‘ ‘, 30 /* | ) */ ‘ ‘, ‘ ‘, ‘ ‘, ‘ ‘, ‘ ‘, ‘ ‘, ‘ ‘, ‘ ‘, ‘ ‘, 31 /* -- \0 */ ‘<‘, ‘<‘, ‘<‘, ‘<‘, ‘<‘, ‘<‘, ‘<‘, ‘ ‘, ‘=‘ 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 ‘\0‘: 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 ( ‘\0‘ == *q ) { *p = ‘\0‘; 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当前长度（以‘\0‘结尾，长度n + 1） 78 char buf[64]; 79 if ( opnd != ( float ) ( int ) opnd ) sprintf ( buf, "%.2f \0", opnd ); //浮点格式，或 80 else sprintf ( buf, "%d \0", ( 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当前长度（以‘\0‘结尾，长度n + 1） 86 rpn = ( char* ) realloc ( rpn, sizeof ( char ) * ( n + 3 ) ); //扩展空间 87 sprintf ( rpn + n, "%c ", optr ); rpn[n + 2] = ‘\0‘; //接入指定的运算符 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:\n");109 while(!opndStk.empty()){110 printf("%.3f ",opndStk.top());111 opndStk.pop();112 }113 }114 void print(stack<char> optrStk){115 printf("optrStk:\n");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 ( "\nexpr:" );124 for ( char* p = expr; ‘\0‘ != *p; p++ ) printf ( " %c", *p ); printf ( " $\nexpr:" );125 for ( char* p = expr; p < pCh; p++ ) printf ( " " );126 if ( ‘\0‘ != * ( pCh - 1 ) )127 { for ( char* p = pCh; ‘\0‘ != *p; p++ ) printf ( " %c", *p ); printf ( " $" ); }128 printf ( "\nexpr:" );129 for ( char* p = expr; p < pCh; p++ ) printf ( "--" ); printf ( " ^\n\n" );130 print ( optrStk ); printf ( "\n" );131 print ( opndStk ); printf ( "\n" );132 printf ( "RPN:\n %s\n\n", rpn ); //输出RPN133 getchar();134 }135 float evaluate ( char* S, char*& RPN ) { //对（已剔除白空格的）表达式S求值，并转换为逆波兰式RPN136 stack<float> opnd; stack<char> optr; //运算数栈、运算符栈 /*DSA*/任何时刻，其中每对相邻元素之间均大小一致137 /*DSA*/ char* expr = S;138 optr.push ( ‘\0‘ ); //尾哨兵‘\0‘也作为头哨兵首先入栈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 ‘=‘: //优先级相等（当前运算符为右括号或者尾部哨兵‘\0‘）时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 }//switch164 displayProgress ( expr, S, opnd, optr, RPN );165 }//while166 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("||====================================================||\n");173 printf("||******************表达式求值************************||\n");174 printf("||***支持加、减、乘、除、乘方、阶乘、左括号、右括号***||\n");175 printf("||====================================================||\n");176 177 printf ( "\nplease scanf the number of evaluate:\n" );178 scanf("%d",&n);179 getchar();//处理第一行末的‘\n‘180 while(n--)181 {182 char str[100];183 system ( "cls" );184 printf ( "\nplease scanf the evaluate:\n" );185 gets(str);//表达式求值（入口）186 printf ( "\nPress [Enter] key to evaluate: [%s]\n", str );getchar();187 char* rpn = ( char* ) malloc ( sizeof ( char ) * 1 ); rpn[0] = ‘\0‘; //逆波兰表达式188 float value = http://www.mamicode.com/evaluate ( removeSpace ( str ), rpn ); //求值189 printf ( "EXPR\t: %s\n", str ); //输出原表达式190 printf ( "RPN\t: [ %s]\n", rpn ); //输出RPN191 printf ( "Value\t= %.3f = %d\n", 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 /* + - * / ^ ! ( ) \0 */ 18 /* -- + */ ‘>‘, ‘>‘, ‘<‘, ‘<‘, ‘<‘, ‘<‘, ‘<‘, ‘>‘, ‘>‘, 19 /* | - */ ‘>‘, ‘>‘, ‘<‘, ‘<‘, ‘<‘, ‘<‘, ‘<‘, ‘>‘, ‘>‘, 20 /* 栈 * */ ‘>‘, ‘>‘, ‘>‘, ‘>‘, ‘<‘, ‘<‘, ‘<‘, ‘>‘, ‘>‘, 21 /* 顶 / */ ‘>‘, ‘>‘, ‘>‘, ‘>‘, ‘<‘, ‘<‘, ‘<‘, ‘>‘, ‘>‘, 22 /* 运 ^ */ ‘>‘, ‘>‘, ‘>‘, ‘>‘, ‘>‘, ‘<‘, ‘<‘, ‘>‘, ‘>‘, 23 /* 算 ! */ ‘>‘, ‘>‘, ‘>‘, ‘>‘, ‘>‘, ‘>‘, ‘ ‘, ‘>‘, ‘>‘, 24 /* 符 ( */ ‘<‘, ‘<‘, ‘<‘, ‘<‘, ‘<‘, ‘<‘, ‘<‘, ‘=‘, ‘ ‘, 25 /* | ) */ ‘ ‘, ‘ ‘, ‘ ‘, ‘ ‘, ‘ ‘, ‘ ‘, ‘ ‘, ‘ ‘, ‘ ‘, 26 /* -- \0 */ ‘<‘, ‘<‘, ‘<‘, ‘<‘, ‘<‘, ‘<‘, ‘<‘, ‘ ‘, ‘=‘ 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当前长度（以‘\0‘结尾，长度n + 1） 45 char buf[64]; 46 if ( opnd != ( float ) ( int ) opnd ) sprintf ( buf, "%.2f \0", opnd ); //浮点格式，或 47 else sprintf ( buf, "%d\0", ( 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当前长度（以‘\0‘结尾，长度n + 1） 54 rpn = ( char* ) realloc ( rpn, sizeof ( char ) * ( n + 3 ) ); //扩展空间 55 sprintf ( rpn + n, "%c", optr ); rpn[n + 2] = ‘\0‘; //接入指定的运算符 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 ‘\0‘: 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 ( ‘\0‘ ); //尾哨兵‘\0‘也作为头哨兵首先入栈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 ‘=‘: //优先级相等（当前运算符为右括号或者尾部哨兵‘\0‘）时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 }//switch125 /*DSA*///displayProgress ( expr, S, opnd, optr, RPN );126 }//while127 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 ( ‘\0‘ == *q ) { *p = ‘\0‘; 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 ( "\nPress any key to evaluate: [%s]\n", str );148 char* rpn = ( char* ) malloc ( sizeof ( char ) * 1 ); rpn[0] = ‘\0‘; //逆波兰表达式149 float value = http://www.mamicode.com/evaluate ( removeSpace ( str ), rpn ); //求值150 ///*DSA*/printf ( "EXPR\t: %s\n", str ); //输出原表达式151 ///*DSA*/printf ( "%s\n", rpn ); //输出RPN152 /*DSA*/printf ( "%d\n",( 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 /* + - * / ^ ! ( ) \0 */ 18 /* -- + */ ‘>‘, ‘>‘, ‘<‘, ‘<‘, ‘<‘, ‘<‘, ‘<‘, ‘>‘, ‘>‘, 19 /* | - */ ‘>‘, ‘>‘, ‘<‘, ‘<‘, ‘<‘, ‘<‘, ‘<‘, ‘>‘, ‘>‘, 20 /* 栈 * */ ‘>‘, ‘>‘, ‘>‘, ‘>‘, ‘<‘, ‘<‘, ‘<‘, ‘>‘, ‘>‘, 21 /* 顶 / */ ‘>‘, ‘>‘, ‘>‘, ‘>‘, ‘<‘, ‘<‘, ‘<‘, ‘>‘, ‘>‘, 22 /* 运 ^ */ ‘>‘, ‘>‘, ‘>‘, ‘>‘, ‘>‘, ‘<‘, ‘<‘, ‘>‘, ‘>‘, 23 /* 算 ! */ ‘>‘, ‘>‘, ‘>‘, ‘>‘, ‘>‘, ‘>‘, ‘ ‘, ‘>‘, ‘>‘, 24 /* 符 ( */ ‘<‘, ‘<‘, ‘<‘, ‘<‘, ‘<‘, ‘<‘, ‘<‘, ‘=‘, ‘ ‘, 25 /* | ) */ ‘ ‘, ‘ ‘, ‘ ‘, ‘ ‘, ‘ ‘, ‘ ‘, ‘ ‘, ‘ ‘, ‘ ‘, 26 /* -- \0 */ ‘<‘, ‘<‘, ‘<‘, ‘<‘, ‘<‘, ‘<‘, ‘<‘, ‘ ‘, ‘=‘ 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当前长度（以‘\0‘结尾，长度n + 1） 45 char buf[64]; 46 if ( opnd != ( float ) ( int ) opnd ) sprintf ( buf, "%.2f\0", opnd ); //浮点格式，或 47 else sprintf ( buf, "%d\0", ( 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当前长度（以‘\0‘结尾，长度n + 1） 53 rpn = ( char* ) realloc ( rpn, sizeof ( char ) * ( n + 3 ) ); //扩展空间 54 sprintf ( rpn + n, "%c", optr ); rpn[n + 2] = ‘\0‘; //接入指定的运算符 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 ‘\0‘: 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 ( ‘\0‘ ); //尾哨兵‘\0‘也作为头哨兵首先入栈 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 ‘=‘: //优先级相等（当前运算符为右括号或者尾部哨兵‘\0‘）时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 }//switch124 /*DSA*///displayProgress ( expr, S, opnd, optr, RPN );125 }//while126 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 ( ‘\0‘ == *q ) { *p = ‘\0‘; 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 ( "\nPress any key to evaluate: [%s]\n", str );148 char* rpn = ( char* ) malloc ( sizeof ( char ) * 1 ); rpn[0] = ‘\0‘; //逆波兰表达式149 float value = http://www.mamicode.com/evaluate ( removeSpace ( str ), rpn ); //求值150 ///*DSA*/printf ( "EXPR\t: %s\n", str ); //输出原表达式151 /*DSA*/printf ( "%s\n", rpn ); //输出RPN152 ///*DSA*/printf ( "Value\t= %.1f = %d\n", 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 /* + - * / ^ ! ( ) \0 */ 17 /* -- + */ ‘>‘, ‘>‘, ‘<‘, ‘<‘, ‘<‘, ‘<‘, ‘<‘, ‘>‘, ‘>‘, 18 /* | - */ ‘>‘, ‘>‘, ‘<‘, ‘<‘, ‘<‘, ‘<‘, ‘<‘, ‘>‘, ‘>‘, 19 /* 栈 * */ ‘>‘, ‘>‘, ‘>‘, ‘>‘, ‘<‘, ‘<‘, ‘<‘, ‘>‘, ‘>‘, 20 /* 顶 / */ ‘>‘, ‘>‘, ‘>‘, ‘>‘, ‘<‘, ‘<‘, ‘<‘, ‘>‘, ‘>‘, 21 /* 运 ^ */ ‘>‘, ‘>‘, ‘>‘, ‘>‘, ‘>‘, ‘<‘, ‘<‘, ‘>‘, ‘>‘, 22 /* 算 ! */ ‘>‘, ‘>‘, ‘>‘, ‘>‘, ‘>‘, ‘>‘, ‘ ‘, ‘>‘, ‘>‘, 23 /* 符 ( */ ‘<‘, ‘<‘, ‘<‘, ‘<‘, ‘<‘, ‘<‘, ‘<‘, ‘=‘, ‘ ‘, 24 /* | ) */ ‘ ‘, ‘ ‘, ‘ ‘, ‘ ‘, ‘ ‘, ‘ ‘, ‘ ‘, ‘ ‘, ‘ ‘, 25 /* -- \0 */ ‘<‘, ‘<‘, ‘<‘, ‘<‘, ‘<‘, ‘<‘, ‘<‘, ‘ ‘, ‘=‘ 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当前长度（以‘\0‘结尾，长度n + 1） 44 char buf[64]; 45 if ( opnd != ( float ) ( int ) opnd ) sprintf ( buf, "%.2f \0", opnd ); //浮点格式，或 46 else sprintf ( buf, "%d\0", ( 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当前长度（以‘\0‘结尾，长度n + 1） 52 rpn = ( char* ) realloc ( rpn, sizeof ( char ) * ( n + 3 ) ); //扩展空间 53 sprintf ( rpn + n, "%c", optr ); rpn[n + 2] = ‘\0‘; //接入指定的运算符 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 ‘\0‘: 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 ( ‘\0‘ ); //尾哨兵‘\0‘也作为头哨兵首先入栈 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 ‘=‘: //优先级相等（当前运算符为右括号或者尾部哨兵‘\0‘）时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 }//switch123 /*DSA*///displayProgress ( expr, S, opnd, optr, RPN );124 }//while125 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 ( ‘\0‘ == *q ) { *p = ‘\0‘; 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]=‘\0‘;148 //for ( int i = 0; i < strlen(str); i++ ) { //逐一处理各命令行参数（表达式）149 ///*DSA*/system ( "cls" ); //150 //printf ( "\nPress any key to evaluate: [%s]\n", str );151 char* rpn = ( char* ) malloc ( sizeof ( char ) * 1 ); rpn[0] = ‘\0‘; //逆波兰表达式152 float value = http://www.mamicode.com/evaluate ( removeSpace ( str ), rpn ); //求值153 ///*DSA*/printf ( "EXPR\t: %s\n", str ); //输出原表达式154 ///*DSA*/printf ( "%s\n", rpn ); //输出RPN155 /*DSA*/printf ( "%.2f\n",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_JUDGE26 // freopen("input.txt", "r", stdin);27 // freopen("output.txt", "w", stdout);28 //#endif29 while (1) printf("%f\n",Evaluate());30 return 0;31 }
表达式求值算法、rpn、1470、1475、1477、1479
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。