中缀表达式转化成后缀表达式的计算

中缀表达式的直接计算,中缀表达式转化成后缀表达式的计算

目 录

一、设计思想……………………………………………………….01

二、算法流程图…………………………………………………….02

三、源代码………………………………………………………….03

四、运行结果……………………………………………………….16

五、遇到的问题及解决…………………………………………….17

六、心得体会……………………………………………………….18

中缀表达式的直接计算,中缀表达式转化成后缀表达式的计算

一、设计思想

第一种算法

先把算术表达式转化成后缀表达式，在对后缀表达式进行计算。

首先建立一个符号栈，用于存放字符和字符的优先级别；然后在建立一个数栈，用于辅助后缀表达式的计算；最后在定义一个字符串数组，用于存放后缀表达式。建立一个计算的函数，该函数用于两个数的计算，在调用这个函数的时候，传入三个参数，两个浮点型参数和一个字符型参数，根据不同的符号进行不同的计算。定义一个判断优先级别的函数，用于判断两个操作符的优先级别，在根据优先级的不同决定不同的操作。

后缀表达式的取得，对算术表达式字符串进行挨个的扫描，如果是数字或者是小数点， 则将数字或者小数点存放到字符数组中，每取完一个数字，则在后面用“|”隔开，如果是操作符，则和栈中得操作符进行比较，若扫描到的符号优先级比栈里的符号优先级低，则栈中元素出栈并存放到字符数组中。每出一个字符到字符数组中就在后面加“|”分隔。继续检查栈顶比较优先级，直到栈中元素优先级比扫描到的符号优先级低或者符号栈为空，则将此操作符入栈。若是“（”则无条件入字符栈，若是“）”则从字符栈中出字符直到遇到“（”为止。当字符数组扫描到最后的时候，计算并没有结束。然后得进行字符栈的判断，看是否已经为空栈，若不是空栈，则出栈字符，将字符存放到数组中。最后字符串数组中存放的就是后缀表达式。得到后缀表达式后，要用数栈进行后缀表达式的计算，后缀表达式的计算中，对新的数组进行从道到尾的扫描，如果遇到数字，以“|”为标记取出完整的操作数，用辅助数组存放，然后转化成浮点数存放到数栈中，遇到“|”则直接将数组下标往后走。遇到字符，则从数栈取出两个数进行计算，将计算的结果从新存放到数栈中，循环直到接到结束。最后存放在数栈中的数就是计算的结果。最后在主函数中调用此函数，进行结果的输出。

第二种算法

对表达式直接进行计算，也称为边走边计算

首先建立一个符号栈，用于存放字符和字符的优先级别；然后建立一个数栈，用于存放数。建立一个计算的函数，该函数用于两个数的计算，在调用这个函数的时候，传入三个参数，两个浮点型参数和一个字符型参数，根据不同的符号进行不同的计算。定义一个判断优先级别的函数，用于判断两个操作符的优先级别，在根据优先级的不同决定不同的操作。 边走边计算实现，扫描算术表达式，如果遇到数字或者是小数点，则进行循环的扫描直到将整个数字从字符数组中取出，把取出的字符存放到一个数组中，在利用c语言的函数把这个字符串的数字转化成浮点型的数字，然后存放到数栈中，若果是字符，则将字符的优先级与字符栈中的字符优先级进行比较，若优先级别低于字符栈中的符号优先级别，则从字符栈中取出操作符，再从数栈中取出两个数字，进行计算，计算的结果存放到数栈中，继续检查符号栈中的元素直到遇到优先级别比扫描到的字符优先级别低或者符号栈为空，将扫描到的符号入栈。。若是“（”则无条件入字符栈，若是“）”则从字符栈中出栈字符从数栈中取数进行计算，直到遇到“（”为止。当字符数组扫描到最后的时候，计算并没有结束。然后得进行字符栈的判断，看是否已经为空栈，若不是空栈，则出栈字符，每出栈一个字符就出栈两个数字，进行计算，直到字符栈空为止。最终存放在数栈中的数就是计算的结果。最后在主函数中调用此函数，进行结果的输出。

中缀表达式的直接计算,中缀表达式转化成后缀表达式的计算

二、算法流程图

第一种算法：先将中缀表达式转化成后缀表达式，然后计算。

图1中缀转后缀流程图

图 2 后缀表达式的计算

中缀表达式的直接计算,中缀表达式转化成后缀表达式的计算

图 3 直接计算中缀表达式

三、源代码

先将中缀表达式转化成后缀表达式，在进行后缀表达式的计算，最后将结果显示。 下面给出的是用第一种算法实现的的程序的源代码：

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

//创建存放字符的结构体

typedef struct

{

int level; char ch; //定义ch 存放操作符 //定义level 存放操作符的优先级

}OpNode;

//创建字符栈

typedef struct

{

OpNode opNode[100];

中缀表达式的直接计算,中缀表达式转化成后缀表达式的计算

int top;

int size; //存放栈顶的数 //存放当前栈的大小

}OpStack;

//对字符栈的初始化

void Op_init(OpStack *ops)

{

} ops->top = 0; ops->size = 0;

//字符栈的入栈操作

void Op_push(OpStack *ops,OpNode op)

{

} ops->size++; ops->opNode[(ops->top)++] = op;

//字符栈的出栈操作

OpNode Op_pop(OpStack *ops)

{

} if(ops->size == 0) { } ops->size--; exit(-1); //判断栈是否为空，如果为空，则退出程序，否则出栈 return ops->opNode[--(ops->top)];

//看字符栈顶操作

OpNode Op_getTop(OpStack *ops)

{

} int len = ops->size; return ops->opNode[len - 1];

//创建存放数的结构体

typedef struct

{

double d; //定义 d 存放操作数

}TdNode;

//创建数栈

typedef struct

{

TdNode tdNode[100]; int size; int top;

}TdStack;

//数栈的初始化

中缀表达式的直接计算,中缀表达式转化成后缀表达式的计算

void Td_init(TdStack *tds)

{

} tds->size = 0; tds->top = 0;

//数栈的入栈

void Td_push(TdStack *tds,TdNode td)

{

} tds->size++; tds->tdNode[(tds->top)++] = td;

//数栈的出栈

TdNode Td_pop(TdStack *tds)

{

if(tds->size == 0) { } exit(-1); //判断栈是否为空，如果为空，则退出程序，否则出栈

} tds->size--; return tds->tdNode[--(tds->top)];

//看数栈栈顶

TdNode Td_getTop(TdStack *tds)

{

} int len = tds->size; return tds->tdNode[len - 1];

//创建一个返回值为double函数，用于两个数的计算，传入三个变量，

//第一个变量为 操作数1，第二个变量为操作数2，第三个变量为操作符

double Cal(double num_1,double num_2,char op)

{

double num = 0; switch(op) { // 定义一个变量用于接收计算的结果 case '+':num = num_1 + num_2;break; case '-':num = num_1 - num_2;break; case '*':num = num_1 * num_2;break;

case '/':if(num_2 == 0) // 如果除数为零，则推出程序并打印错误信息

{ } num = num_1 / num_2; printf("\ndivisor zero can't"); exit(-1); else

中缀表达式的直接计算,中缀表达式转化成后缀表达式的计算

} } return num;

//创建一个返回值为int型的函数，用于比较两个操作符的优先级

int Compare_opeate(int level_1,int level_2)

{

} if(level_1 >= level_2) //判断优先级别，返回相应的值 return 0; return -1;

//创建一个返回值为double型的函数，用于返回整个表达式的计算结果

double CalResult()

{

//char ch[] = "23+12-34"; //char ch[] = "19-(2*3)+12/2"; char ch[] = "(23-3)/0+12*2";

char tempCh[100]; //存放后缀表达式

int index = 0,i = 0;

OpStack ops;

//定义 操作符栈 TdStack tds; //定义 操作数栈 OpNode op; //定义 字符节点 TdNode td; //定义 数节点 Op_init(&ops); //初始化字符栈 Td_init(&tds); //初始化操作数栈 while(ch[index] != '\0') { char chr = ch[index]; if(chr >= '0' && chr <= '9' || chr == '.') {

} int tempIndex = index; while(chr >= '0' && chr <= '9' || chr == '.') //判断是否为操作数 { } tempCh[i++] = '|'; //在一个操作数取完之后，后面加分隔符 index = tempIndex; continue; tempCh[i++] = ch[tempIndex]; tempIndex++; chr = ch[tempIndex];

//判断是否为加法或者减法运算 if(chr == '+' || chr == '-') {

op.ch = chr; //存放操作符到操作符节点

中缀表达式的直接计算,中缀表达式转化成后缀表达式的计算

op.level = 2; //给操作符赋值优先级 int level_2 = 2; //存放优先级别，用于比较优先级 while(ops.size != 0) //若字符栈不为空，则进行字符的优先级比较 { int level_1 = Op_getTop(&ops).level; //两个字符比较优先级，若新的字符优先级比栈中的字符优先级高，则 //从字符栈中字符出栈，将出栈的字符放到后续数组中

}

if(ops.size == 0) //若字符栈是空栈，则直接进行入栈的操作

{

}

index++;

continue; Op_push(&ops,op); if(Compare_opeate(level_1,level_2) == 0) { } else { } Op_push(&ops,op); break; char op1 = Op_pop(&ops).ch; tempCh[i++] = op1; tempCh[i++] = '|';

}

//判断是否为乘法或者除法的运算符 if(chr == '*' || chr == '/') {

op.ch = chr; //存放操作符到操作符节点 op.level = 3; //给操作符赋值优先级

int level_2 = 3; //存放优先级别，用于比较优先级

while(ops.size != 0)

{

int level_1 = Op_getTop(&ops).level;

//两个字符比较优先级，若新的字符优先级比栈中的字符优先级高，则 //从字符栈中字符出栈，将出栈的字符放到后续数组中 if(Compare_opeate(level_1,level_2) == 0) { } else char op1 = Op_pop(&ops).ch; tempCh[i++] = op1; tempCh[i++] = '|';

中缀表达式的直接计算,中缀表达式转化成后缀表达式的计算

}

if(ops.size == 0) //若字符栈是空栈，则直接进行入栈的操作

{

}

index++;

continue; Op_push(&ops,op); { } Op_push(&ops,op); break;

}

//判断是否为左括号，直接进行入栈操作 if(chr == '(') { } op.ch = chr; op.level = -1; Op_push(&ops,op); index++; continue;

//判断是否为右括号 if(chr == ')') { char ch1 = Op_getTop(&ops).ch;

} } //进行出栈的操作，知道遇到左括号为止。将出栈的字符加入后续字符中 while(ch1 != '(') { } Op_pop(&ops); index++; continue; char op1 = Op_pop(&ops).ch; tempCh[i++] = op1; tempCh[i++] = '|'; ch1 = Op_getTop(&ops).ch;

//如果字符栈不为空，则一直出栈直到字符栈为空。 while(ops.size != 0) { char op1 = Op_pop(&ops).ch; tempCh[i++] = op1; tempCh[i++] = '|';

中缀表达式的直接计算,中缀表达式转化成后缀表达式的计算

}

tempCh[i++] = '\0'; //最后在字符数组中加字符的结束标志 \0

int j = 0; //打印后缀表达式 printf("follow-up expression: "); while(tempCh[j] != '\0') { } printf("%c",tempCh[j]); j++;

int k = 0;

//将后缀表达式进行计算 while(tempCh[k] != '\0') { char cc = tempCh[k];

if(cc >= '0' && cc <= '9' || cc == '.') //判断是否为操作数

{

int tempIndex = k; int i = 0;

char assch[10] ={0}; //定义数组存放一个操作数，并进行初始化

while(cc >= '0' && cc <= '9' || cc == '.')

{

}

td.d = atof(assch);

Td_push(&tds,td); //将取出的操作数入栈

k = tempIndex;

continue; assch[i++] = tempCh[tempIndex]; tempIndex++; cc = tempCh[tempIndex];

}

else if(cc == '|') // 如是 | 则直接跳过 { } else // 如果是字符，则出栈两个数 进行计算

{

char op1 = cc; double num_2 = Td_pop(&tds).d; double num_1 = Td_pop(&tds).d; double num = Cal(num_1,num_2,op1); td.d = num; k++;

中缀表达式的直接计算,中缀表达式转化成后缀表达式的计算

} } Td_push(&tds,td); k++;

} return Td_pop(&tds).d;

main()

{

double result = CalResult(); //调用函数，得到计算的结果

} printf("\nResult is ："); printf("%.2f",result);

第二种算法对中缀表达式直接进行计算，并将结果输出，实现的源代码：

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

//创建存放字符的结构体

typedef struct

{

char ch; //定义ch 存放操作符

int level; //定义level 存放操作符的优先级

}OpNode;

//创建字符栈

typedef struct

{

OpNode opNode[100]; int top; int size; //存放栈顶的数 //存放当前栈的大小

}OpStack;

//对字符栈的初始化

void Op_init(OpStack *ops)

{

} ops->top = 0; ops->size = 0;

//字符栈的入栈操作

void Op_push(OpStack *ops,OpNode op)

{

} ops->size++; ops->opNode[(ops->top)++] = op;

中缀表达式的直接计算,中缀表达式转化成后缀表达式的计算

//字符栈的出栈操作

OpNode Op_pop(OpStack *ops)

{

if(ops->size == 0) {

}

ops->size--; exit(-1); //判断栈是否为空，如果为空，则退出程序，否则出栈

} return ops->opNode[--(ops->top)];

//看字符栈顶操作

OpNode Op_getTop(OpStack *ops)

{

} int len = ops->size; return ops->opNode[len - 1];

//创建存放数的结构体

typedef struct

{

double d; //定义 d 存放操作数

}TdNode;

//创建数栈

typedef struct

{

TdNode tdNode[100]; int size; int top;

}TdStack;

//数栈的初始化

void Td_init(TdStack *tds)

{

} tds->size = 0; tds->top = 0;

//数栈的入栈

void Td_push(TdStack *tds,TdNode td)

{

} tds->size++; tds->tdNode[(tds->top)++] = td;

//数栈的出栈

TdNode Td_pop(TdStack *tds)

{

if(tds->size == 0) //判断栈是否为空，如果为空，则退出程序，否则出栈

中缀表达式的直接计算,中缀表达式转化成后缀表达式的计算

} } tds->size--; return tds->tdNode[--(tds->top)]; exit(-1);

//看数栈栈顶

TdNode Td_getTop(TdStack *tds)

{

} int len = tds->size; return tds->tdNode[len - 1];

//创建一个返回值为double函数，用于两个数的计算，传入三个变量，

//第一个变量为 操作数1，第二个变量为操作数2，第三个变量为操作符

double Cal(double num_1,double num_2,char op)

{

} double num = 0; // 定义一个变量用于接收计算的结果 switch(op) { } return num; case '+':num = num_1 + num_2;break; case '-':num = num_1 - num_2;break; case '*':num = num_1 * num_2;break; case '/':if(num_2 == 0) // 如果除数为零，则推出程序并打印错误信息 { } num = num_1 / num_2; printf("divisor zero can't"); exit(-1); else

//创建一个返回值为int型的函数，用于比较两个操作符的优先级

int Compare_opeate(int level_1,int level_2)

{

} if(level_1 >= level_2)//判断优先级别，返回相应的值 return 0; return -1;

//创建一个返回值为double型的函数，用于返回整个表达式的计算结果

double CalResult()

{

//char ch[] = "23+12-34";

中缀表达式的直接计算,中缀表达式转化成后缀表达式的计算

//char ch[] = "(23-3)/2+12*2"; int index = 0; //定义字符串的索引

//定义 操作符栈 TdStack tds; //定义 操作数栈 OpNode op; //定义 字符节点 TdNode td; //定义 数节点 Op_init(&ops); //初始化字符栈 Td_init(&tds); //初始化操作数栈 OpStack ops; while(ch[index] != '\0') {

char chr = ch[index]; //取出字符串的而一个字符 if(chr >= '0' && chr <= '9' || chr == '.') //判断是否为操作数 { int tempIndex = index; //定义辅助索引 int i = 0; } //定义数组存放一个操作数，并进行初始化 //将一个操作数从字符数组中取出，并存放在tempCh数组中 char tempCh[10] ={0}; while(chr >= '0' && chr <= '9' || chr == '.') { } td.d = atof(tempCh); Td_push(&tds,td); index = tempIndex; continue; tempCh[i++] = ch[tempIndex]; tempIndex++; chr = ch[tempIndex]; //把取出的操作数存放到操作数栈

//判断是否为加法或者减法运算 if(chr == '+' || chr == '-') {

//存放操作符到操作符节点 op.level = 2; //给操作符赋值优先级 int level_2 = 2; //存放优先级别，用于比较优先级 while(ops.size != 0) //若字符栈不为空，则进行字符的优先级比较 { int level_1 = Op_getTop(&ops).level; op.ch = chr; //两个字符比较优先级，若新的字符优先级比栈中的字符优先级高，则 //从字符栈中字符出栈，同时从数栈中出栈两个数，进行计算，计算结 //果存入数栈,否则将新的字符入栈 if(Compare_opeate(level_1,level_2) == 0) { char op1 = Op_pop(&ops).ch;

中缀表达式的直接计算,中缀表达式转化成后缀表达式的计算

} } if(ops.size == 0) //若字符栈是空栈，则直接进行入栈的操作 { } index++; continue; Op_push(&ops,op); } else { } Op_push(&ops,op); break; double num_1 = Td_pop(&tds).d; double num = Cal(num_1,num_2,op1); td.d = num; Td_push(&tds,td);

//判断是否为乘法或者除法的运算符 if(chr == '*' || chr == '/') {

op.ch = chr; //存放操作符到操作符节点 op.level = 3; //给操作符赋值优先级 int level_2 = 3; //存放优先级别，用于比较优先级 while(ops.size != 0) { int level_1 = Op_getTop(&ops).level;

//两个字符比较优先级，若新的字符优先级比栈中的字符优先级高，则 //从字符栈中字符出栈，同时从数栈中出栈两个数，进行计算，计算结 //果存入数栈,否则将新的字符入栈 if(Compare_opeate(level_1,level_2) == 0) { } else { Op_push(&ops,op); break; char op1 = Op_pop(&ops).ch; double num_2 = Td_pop(&tds).d; double num_1 = Td_pop(&tds).d; double num = Cal(num_1,num_2,op1); td.d = num; Td_push(&tds,td);

中缀表达式的直接计算,中缀表达式转化成后缀表达式的计算

}

if(ops.size == 0) //若字符栈是空栈，则直接进行入栈的操作

{

}

index++;

continue; Op_push(&ops,op);

}

//判断是否为左括号，直接进行入栈操作 if(chr == '(') { } op.ch = chr; op.level = -1; Op_push(&ops,op); index++; continue;

//判断是否为右括号 if(chr == ')') { char ch1 = Op_getTop(&ops).ch;

} } //进行出栈的操作，知道遇到左括号为止。 while(ch1 != '(') { } Op_pop(&ops); index++; continue; char op1 = Op_pop(&ops).ch; double num_2 = Td_pop(&tds).d; double num_1 = Td_pop(&tds).d; double num = Cal(num_1,num_2,op1); td.d = num; Td_push(&tds,td); ch1 = Op_getTop(&ops).ch;

//如果字符栈不为空，则一直出栈直到字符栈为空。 while(ops.size != 0) { char op1 = Op_pop(&ops).ch; double num_2 = Td_pop(&tds).d; double num_1 = Td_pop(&tds).d;

中缀表达式的直接计算,中缀表达式转化成后缀表达式的计算

} td.d = num; Td_push(&tds,td);

} //将结果出栈返回 return Td_pop(&tds).d;

main()

{

} double result = CalResult(); //调用函数，得到计算的结果 printf("Result is :"); printf("%.2f",result);

四、运行结果

中缀表达式直接进行计算的运行结果如下：

图 4 中缀表达式直接计算

后缀转中缀再进行计算的运行结果如下：

图 5 后缀表达式计算结果

中缀表达式的直接计算,中缀表达式转化成后缀表达式的计算

五、遇到的问题及解决

问题1：从字符数组中截取出数字的操作，并转化成浮点型的数不正确。计算的结 果有时候是一个意想不到的很大的数。

问题1的解决方法：从字符数数组中将数字截取出来就是为了能进行计算，而数字是单个字符的形式存在，必须把一个完整的数从算术表达式中截取出来，如果遇到数字的字符就是一个数字的入口，然后循环取出直到遇到不是数字或者小数点为止。而这些取出的数字是一堆离散的数字字符。这时候就需要建立一个辅助的数组来存放这些数字字符以组成一个数字的字符。用一个辅助的索引将数字的组成字符一个一个从数组中取出来，存放到新的数组中，以得到一个字符串的数字。从数组中截取出一个数后，将取出的数用atof 函数进行转化成浮点型的数。在把浮点型的数存放到数栈中，在后面的计算中取出。在调试中第一个取出的浮点型数是正确的，当遇到后面截取的数的长度比第一个数短的时候，发现取出的数和第一个数的位数相同了。经过分析，每次截取完数字后并没有对辅助数组进行重新的初始化，数组中宗存放着前一个字符，一旦遇到数字比前面的数字短的的情况，后面的数字只覆盖了前面的数字的前几位，后面的几位都是原先的数字。造成取出的结果是错误的。解决问题的方法可以在每次存放数字之前，把辅助数组进行初始化，结果能正确计算表达式。

问题2：如何生成后缀表达式，将数与字符存放在一个字符串中。

问题2的解决方法：想把数字从字符数组中取出来，然后再存入后缀表达式中，从 字符数组中取出是很容易的，但是在把这些数字和操作符进行存入一个后缀表达式数 的时候出现了问题，因为c 语言中没有这样的字符数组，所以取出的数字根本没法和操作符一块存到一个数组中去。改变一种想问题的方法，就是不把字符数组的数字都截取出来，而是把数字进行一个分割，让数字还依旧存放在数组中，只是在每个数字的后面都加上一个分割符号“|”，然后要是遇到操作符也将操作符存放到这个数组中并且也加入分隔符，这样就组成了一个全新的数组，也即是后缀表达式。这里的修改是遇到数字，边走边存，一个数字取完后就在数字的后面加分隔符。如果是操作符，则进行优先级的判断，根据判断的结果把操作符加入到数组中，以生成后缀表达式。对新生成的后缀表达式数组在进行计算，在后缀表达式中将数字截取出来，这样子做的效果比原先就截取出来好实现。通过扫面后缀表达式，根据分隔符可以很简单的就截取出一个数字字符串，再把字符串数字转化成浮点数存放到数栈中，遇到操作符就计算，从数栈中取出两个数字，连同操作一起调用函数进行计算。循环扫描，直到扫描到“\0”，最后将结果从数栈中取出作为结果返回给主函数。

问题3：如何解决除数是零的问题

问题3的解决方法：在进行除法运算的时候，遇到除数为 0 的情况肯定是特殊处 理的，但是该如何让程序在遇到这个问题的时候退出程序，并输出提示错误的信息。 这时候需要用到一个c 语言里面自带的一个函数，如果是除数为零的情况就调用函数exit（-1），给赋值为-1的时候就能正确低从程序中跳出来，只要在跳出之前打印错误的信息就可以达到想要的效果了。

中缀表达式的直接计算,中缀表达式转化成后缀表达式的计算

六、心得体会

通过这两个程序的编写，我发现了学习上的挺多问题，尤其在遇到指针的问题的时候，很茫然，以后在学习中要多注意指针的使用，以达到熟练掌握的程度，平时的学习中一定要多写程序，多写一些才回把知识用得自然。

其实大一就开始学习C语言，可是，当时学的时候就觉得语言好像是学会了，可是一遇到编程的问题还是头大，总感觉没有什么思路，而这次作业，给自己一个不得不动手操作的机会，在十一的这几天中，复习了以前学过的C的基本知识，然后一点一点的摸索，遇到了错误和同学一起讨论，有问题自己想办法解决，最后程序调试出来的时候，会觉得真的很高兴。我知道，我们现在的水平还很差，要想学习好这门课，在以后就要多动手操作，书上的例题或算法，最好都自己编写程序实现，那样可以加深对算法的理解，也可以提高我们编程的水平。

同时，很多的东西，理解了，可是在实现的时候还是有很多的错误发生，在以后的练习和实践中，应该多动手，遇到问题多思考，即使方案不是最优的也要想办法自己解决，然后和好的方案进行比较，从中找出自己的差距在哪里。

本文来源：https://www.bwwdw.com/article/tk94.html