表达式求值"/>
C语言 栈的应用----表达式求值
栈的应用----表达式求值
用栈的方式实现中缀表达式转后缀表达式:
初始化一个栈,用于保存暂时还不能确定运算顺序的运算符。从左到右处理各个元素,直到末尾。可能遇到以下三种情况:
- 遇到操作数,直接加入后缀表达式。
- 遇到界限符,遇到“(”直接入栈,遇到“)”则依次弹出栈内运算符并加入后缀表达式,直到弹出“(”为止。注意:“(” 不加入后缀表达式。
- 遇到运算符。依次弹出栈中优先级高于或等于当前运算符的所有运算符,并加入后缀表达式,若碰到“(”或栈空则停止,之后再把当前运算符入栈。
按上述方法处理完所有字符后,将栈中剩余运算符依次弹出,并加入后缀表达式。用栈实现中缀表达式的计算:
- 初始化两个栈,操作数栈和运算符栈;
- 若扫描到操作数,压入操作数栈;
- 若扫描到运算符或界限符,则按照“中缀转后缀”相同的逻辑压入运算符栈(期间也会弹出运算符,每当弹出一个运算符时,就需要再弹出两个操作数栈的栈顶元素并执行相应运算,运算结果再压回操作数栈;
/*栈的应用----表达式求值。
*/
#include <stdio.h> // 引用输入(scanf)、输出(printf)函数的头文件;
#include <stdlib.h> // 引用 malloc free 函数的头文件; //构建栈的结构
typedef struct LinkNode{char str;LinkNode *next;
}LinkNode, *LinkStack; //栈的初始化
void InitStack(LinkStack &S)
{S = NULL;
}//栈空的判断
bool EmptyStack(LinkStack S)
{if (S == NULL)return true;elsereturn false;
}//进栈操作;单链表的前插操作
void InsertStack(LinkStack &S, char str)
{LinkNode *p; //定义一个指针结点; p = (LinkNode *)malloc(sizeof(LinkNode)); //分配空间; p->str = str; //赋值该节点的str属性值; p->next = S; S = p; //修改 S 的指向
}//出栈操作
bool DeleteStack(LinkStack &S, char &str)
{if (EmptyStack(S)) //栈空报错; return false;LinkNode *p = S; //定义一个指针结点,使其指向要被删除的栈顶结点; str = p->str; //用str记录要被弹出栈的元素值,并传递出去; S = p->next; //修改S指针指向的位置; free(p); //释放要被删除的结点 return true;
}//获取栈顶元素,用str传递栈顶元素;
bool GetStack(LinkStack S, char &str)
{if (EmptyStack(S)) //栈空报错; return false;str = S->str;return true;
}//进行 + - * / 运算,将计算结果用Lnum传递;
bool Operation(char &Lnum, char Rnum, char operation)
{switch (operation){case '+':Lnum = Lnum + Rnum;break;case '-':Lnum = Lnum - Rnum;break;case '*':Lnum = Lnum * Rnum;break;case '/':if (Rnum == 0){printf("除数不能为0!\n");return false;}Lnum = Lnum / Rnum;break;default:printf("有不合法的运算符!\n");return false; break;}return true;
} //比较运算符的顺序;用result传递比较结果;
bool Compare(char one, char topchar, char &result)
{switch (one){case '+':case '-':if (topchar == '(')result = '<'; //'+' '-' 进栈; elseresult = '>'; break;case '*':case '/':if (topchar == '*' or topchar == '/')result = '>';elseresult = '<'; //'*' '/' 进栈; break;case '(':result = '<';break;case ')':result = '=';break;default :printf("有不合法的运算符!\n"); return false;break;}return true;
}int main()
{LinkStack Snum, Schar;InitStack(Snum); //初始化操作数栈; InitStack(Schar); //初始化运算符栈; printf("Function:\n"); printf("栈的应用-----表达式求值\n");printf("input what you want to calculator:");char *op = (char *)malloc(sizeof(char)); //为指针op分配空间; gets(op); //赋值;char topstr,result; //记录栈顶符号和比较之后的结果; char Lnum,Rnum; //记录左,右操作数; while (*op) //循环指针op,直到找到结束符'\0'结束; {//如果此时是操作数,循环判断下一位是否是数字; if (*op >= '0' and *op <= '9'){char num = 0; //eg:读入数据是19,则从左到右读取:1*10+9; while (*op >= '0' and *op <= '9'){num = *op - '0' + num * 10;*op++;}InsertStack(Snum,num); //将操作数入栈; *op--; //恢复上一个指针指向; }else if (*op == '+' or *op == '-' or *op == '*' or *op == '/' or *op == '(' or *op == ')') {//比较操作大小,再考虑是否入栈或者进行计算;if (!EmptyStack(Schar)) //栈不为空; { GetStack(Schar, topstr); //获取栈顶操作符; Compare(*op, topstr, result);switch (result) {case '>'://弹出栈顶操作符,进行运算;DeleteStack(Schar,topstr);if (!DeleteStack(Snum,Rnum)){printf("右操作数匹配失败。\n");return 1;}if (!DeleteStack(Snum,Lnum)){printf("左操作数匹配失败。\n");return 1;} if (!Operation(Lnum,Rnum,topstr))return 1;InsertStack(Snum,Lnum); //将计算后的结果重新放入操作数栈; InsertStack(Schar,*op); //将操作符放入操作符栈; break;case '<':InsertStack(Schar, *op); //将操作符入栈;break;case '='://弹出栈顶操作符,进行运算,直到找到‘(’;GetStack(Schar,topstr); //读取栈顶操作符; while(topstr != '(') {DeleteStack(Schar,topstr);if (!DeleteStack(Snum,Rnum)){printf("右操作数匹配失败。\n");return 1;}if (!DeleteStack(Snum,Lnum)){printf("左操作数匹配失败。\n");return 1;} if (!Operation(Lnum,Rnum,topstr))return 1;InsertStack(Snum,Lnum); //将计算后的结果重新放入操作数栈; GetStack(Schar,topstr); //读取栈顶操作符;}DeleteStack(Schar,topstr);break;}}else{//栈空操作符直接进栈; InsertStack(Schar, *op); //将操作符入栈;} }else if(*op != ' ') //完善程序的健壮性,不是空格符报错; {printf("发现不法符号!退出程序。\n");return 1; } *op++;}while(!EmptyStack(Schar)) {//弹出栈顶操作符,进行运算;DeleteStack(Schar,topstr);if (!DeleteStack(Snum,Rnum)){printf("右操作数匹配失败。\n");return 1;}if (!DeleteStack(Snum,Lnum)){printf("左操作数匹配失败。\n");return 1;} if (!Operation(Lnum,Rnum,topstr))return 1;InsertStack(Snum,Lnum); //将计算后的结果重新放入操作数栈;}DeleteStack(Snum,topstr);printf("%d",topstr); return 0;
}
写在后面:代码稍微有点长,有许多需要改善的地方,有其他问题留言相互交流学习;
更多推荐
C语言 栈的应用----表达式求值
发布评论