JZTXT

表达式求值

发布时间 2023-08-10 14:30:17作者: wljss
void transform(char suffix[ ], char exp[ ] ) 
{
	// 从合法的表达式字符串exp求得其相应的后缀式字符串suffix，
	// precede(a,b)判别算符法的优先程度，当a的优先数≥b 的优先数时，返回 1，否则返回0
	InitStack(S);      Push(S, '#');                   // 预设运算符栈的栈底元素为'#'
	p = exp;      ch = *p;       k=0;
	while (!StackEmpty(S)) 
	{
		if (!OpMember(ch))   Suffix[k++] = ch;       // 操作数直接发送给后缀式
		else 
		{
			switch (ch) 
			{
				case '(' : Push(S, ch); break;            // 左括弧一律入栈
				case ')' : 
					{
						Pop(S, c);
						while (c!= '(' )            // 自栈顶至左括弧之前的运算符发送给后缀式
						{
							Suffix[k++] = c;  Pop(S, c) 
						}
						break; 
					}
				default : 
					{
						while( Gettop(S, c) && ( precede(c,ch)) ) 
						{              
							Suffix[k++] =c;  Pop(S, c); 
						}  // 将栈中所有优先数不小于当前运算符优先数的运算符发送给后缀式
						if ( ch!= '#' )  Push( S, ch);           // 优先数大于栈顶的运算符入栈
						break;
					} 
			}
		}
		if ( ch!= '#' ) ch = *++p;  
	} 
	Suffix[k] = '\0' ;                             // 添加字符串的结束符
}

题目
https://www.luogu.com.cn/problem/P1449
https://www.luogu.com.cn/problem/P1981