C语言栈的应用----表达式求值

编程入门行业动态更新时间:2024-10-24 18:21:15

C语言栈的应用----<a href=https://www.elefans.com/category/jswz/34/1771310.html style= 表达式求值"/>

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;
}