http://www.Sina.com/http://www.Sina.com /
第一，将骑马订表达式转换为后缀表达式(反波兰表达式)，然后对后缀表达式进行评估
第二，使用两个堆栈直接评价
以下是两种方法中缀表达式求值
1、利用堆栈将骑马订式转换为后缀式
2、之后，利用堆栈求后缀表达式的值
【应对步骤的具体操作】
1、首先将骑马订形式转换为后缀形式。 (注意：在骑马订表达式中，数字和运算符之间没有空格。 转换为后缀表达式后，数字和运算符、数字和数字、运算符和运算符之间存在空格，因此很容易进行运算。 ）
(1)顺序扫描骑马钉式
)2)遇到数字输出到后缀的表达式
)3)遇到运算符可能有以下情况
a:堆栈空直接堆栈
b:遭遇’(直接进入堆栈
c:遇到’()、)、)、)、)、)、堆栈输出)、)、)、不作为输出)，因为后缀表达式中没有括号)。
如果d:运算符的优先级高于堆栈顶部运算符的优先级，则将其放入堆栈
如果运算符的优先级小于或等于堆栈顶部运算符的优先级，则e:离开堆栈并停止，直到优先级高于堆栈顶部运算符的优先级，然后进入堆栈
2、计算后缀表达式
(1)依次扫描后缀表达式
)2)遇到数值输入堆栈
(3)遇到符号后，适当运算堆栈开头的两个要素，将运算结果重新进入堆栈，直到扫描结束)1) )重复操作
【导线安装】
# include stdio.h # define maxsize 100//判定式的优先顺序intsymCMP(chara，char b ) ) if(b==' () ) return 1； elseif((b=='*'|b=='/' ) ) a=='|a='-'|'|| a=' ) ) () ) ) rn1； elseif((b==''|b=='-' ) (a==' ) ) ) )返回1； elsereturn 0； //骑马订式为后缀式voidexp_transplant(char*str1，char *str2) {char stack[MAXSIZE]； //堆栈int top=-1； //堆栈顶部指针int j=0； for(intI=0； str1[i]！=' '； I () if ) str1[I]='0'str1[I]='9' ) /数字直接输出str2[j ]=str1[i]； ELSE{if(I！=0 str2[j - 1]！=' ' )//之间的空格str2[j ]=' '； if(str1[I]==' () ) () ) ) ) )进行堆叠并输出，但不输出) ) (while (堆叠[顶部]！=' ' () ({ str2[ j ]=堆叠[ top-- ]； str2[j ]=' '； }top----； }else if (！ sym CMP (堆栈[顶层]，str1[i] ) /如果运算符优先级低，则堆栈{ while (顶层-1(！ sym CMP (堆栈[顶部]，str1[i] ) /如果堆栈为空或优先级高，则停止堆栈) { str2[ j ]=堆栈[顶部--] )； str2[j ]=' '； }堆叠[ top ]=str1[ I ]； } else {堆叠[ top ]=str1[ I ]； }}if(str2[j-1]！=' ' ) str2[j ]=' '； while(top-1 ) /输出堆栈中的其余运算符({ str2[ j ]=堆栈[ top-- ]； str2[j ]=' '； }str2[j - 1]=' '； //便于以后计算后缀表达式}//后缀表达式intcal_s(char*str ) intstack(maxsize )； int top=-1，tmp=0，k=10； for(intI=0； str[i]！=' '； I ) if(str[I]='0'str[I]='9' ) /计算值tmp=tmp * 10 str[i] - '0)； else if (遇到str [ I ]==' ' (/' )时进入堆栈(包含上一个for循环的tmp值({堆栈[ top ]=tmp； tmp=0； 设置为//0以计算下一个数值(}else //运算符进入并使用堆栈顶部的两个元素进行相应的运算) switch(str ) I ) case ' ' : tmp=stack (堆栈-1) 布雷克； case '-' : tmp=堆叠[ top-1 ] -堆叠[ top ]； 布雷克； case ' * ' : tmp=堆叠[ top-1 ] *堆叠[ top ]； 布雷克； case '/' : tmp=堆叠[ top-1 ] /堆叠[ top ]； 布雷克； }top -=2； }}sta
ck[++top] = tmp; //后缀表达式中最后一个运算符后没有空格，所有整个表达式的最后结果就没有入栈return stack[0];}//计算中缀表达式int calculate_expression(char *str){char s[100]; //存放后缀表达式exp_transplant(str, s); //将中缀表达式转换为后缀表达式int ret = cal_s(s); //计算后缀表达式return ret;}int main(){char *str = "50+7*3*(2+1)-3";int ret = calculate_expression(str);printf("表达式的结果是：%dn", ret);return 0;}第二种：
利用两个栈直接求结果，一个是运算值栈（数值入的栈），一个是运算符栈（运算符入的栈）
【对应步骤具体操作】
（1）依次扫描中缀表达式
（2）遇到运算值直接入栈
（3）遇到运算符，有以下几种情况
a:栈空直接入栈
b:遇到’(‘直接入栈
c:遇到’)‘一直出栈并拿运算值栈中的栈顶两个元素做相应的运算，直到’('出栈为止。（栈顶两个元素运算时注意次序，栈顶第二个运算值在前，第一个在后，例如：a为栈顶元素，b为此栈顶元素，两值做减法运算，b-a）
d:遇到运算符优先级高于栈顶运算符优先级，则入栈
e:遇到运算符优先级低于或等于栈顶运算符优先级，则出栈，直到其优先级高于栈顶运算符优先级时停止（或栈为空）,最后再将其入栈
f:直到中缀表达式扫描结束
（4）中缀表达式扫描结束后，如果运算符栈中还有运算符，一直出栈并与运算值栈做相应操作（与步骤(3)中c的操作相同），直到栈空
（5）此时运算值栈中剩一个元素，即为最终结果
【代码实现】
#include <stdio.h>#include <ctype.h>#define MAXSIZE 100//判断表达式的优先级int symcmp(char a, char b){if (b == '(')return 1;else if ((b == '*' || b == '/') && (a == '+' || a == '-' || a == '('))return 1;else if ((b == '+' || b == '-') && (a == '('))return 1;elsereturn 0;}//计算运算值栈顶两个元素(a栈顶第一个元素，b栈顶第二个元素)int calculate(char c,int a,int b){int tmp = 0;switch (c){ case '+':tmp = b + a; break; case '-':tmp = b - a; break; case '*':tmp = b * a; break; case '/':tmp = b / a; break;}return tmp;}//计算中缀表达式int calculate_expression(char *str){int num_stack[MAXSIZE]; //运算值栈int num_top = -1; //运算值栈指针char sym_stack[MAXSIZE]; //操作符栈int sym_top = -1; //操作符栈指针int i = 0;while (str[i] != ' '){if (isdigit(str[i]))//判断是否是数字字符{//将数字字符转换为数值型并入栈 int val = 0;while (isdigit(str[i])){val = val * 10 + str[i] - '0';i++;}num_stack[++num_top] = val;}else //符号{if (str[i] == ')'){while (sym_stack[sym_top] != '('){int ret = calculate(sym_stack[sym_top], num_stack[num_top], num_stack[num_top - 1]); //计算栈顶两个元素sym_top--;num_top -= 2;num_stack[++num_top] = ret;}sym_top--;i++;}else if (!symcmp(sym_stack[sym_top], str[i])){while (sym_top > -1 && (!symcmp(sym_stack[sym_top], str[i]))){int ret = calculate(sym_stack[sym_top], num_stack[num_top], num_stack[num_top - 1]); //计算栈顶两个元素sym_top--;num_top -= 2;num_stack[++num_top] = ret;}sym_stack[++sym_top] = str[i];i++;}else{sym_stack[++sym_top] = str[i];i++;}}}while (sym_top > -1){int ret = calculate(sym_stack[sym_top], num_stack[num_top], num_stack[num_top - 1]); //计算栈顶两个元素sym_top--;num_top -= 2;num_stack[++num_top] = ret;}return num_stack[0];}int main(){char *str = "50+3*(2+1)-5*5*(5+5)";int ret = calculate_expression(str);printf("表达式的结果是：%dn", ret);return 0;}OK!!!到此结束。如果有什么问题，希望友友们多多指教，共同进步！加油！加油！加油！