PTA第4周——5 后缀表达式

题目:

所谓后缀表达式是指这样的一个表达式:式中不再引用括号,运算符号放在两个运算对象之后,所有计算按运算符号出现的顺序,严格地由左而右进行(不用考虑运算符的优先级)。

如:中缀表达式 3*(5–2)+7 对应的后缀表达式为:352-*7+ 。

请将给出的中缀表达式转化为后缀表达式并输出。

输入格式:

输入仅一行为中缀表达式,式中所有数字均为个位数,表达式长度小于1000。

输出格式:

输出一行,为后缀表达式,式中无空格。

输入样例:

2+4*8+(8*8+1)/3

输出样例:

248*+88*1+3/+

题意分析:

将中缀表达式改写为后缀表达式。

解题思路:

转化规则:

            从左到右读表达式,对于扫描到的数字直接输出,对于扫描到的运算符:

            首先对运算符按照优先级分为:

                    1级——>‘+’, ‘-’

                    2级——>‘*’, ‘/’

            还有两个特殊的:

                    左括号:‘(’

                    右括号:‘)’

            如果栈是空的话,则无论读到的是什么运算符都直接存入栈中。

            如果读到的运算符是 左括号‘(’,则直接存入栈中。并且其之后读取的第一个运算符也可以直接存进来。

            如果读到的运算符是 右括号‘)’,则把栈中最靠近栈底的 左括号‘(’ 前 【包括左括号】 的所有运算符都依次打印【不需要打印左括号】并且移除栈

            对于其他情况,当  本次读取到的运算符的优先级<= 栈顶运算符的优先级   时,将栈顶运算符输出并移除栈。直到 本次读取到的运算符优先级 > 栈顶运算符优先级 或者 栈顶运算符为  左括号‘(’  。此时将读取到的字符存入栈里。

            最后如果栈非空,则依次输出栈中所有的运算符。
基于上述规则,会发现真正存的进栈的只有 +-*/( 。同时为了避免之后栈非空的讨论,在建立栈的时候就先存了一个‘(’,在中缀表达式字符串后加了一个‘)’。相当于在表达式最外面套了一对括号。

具体算法流程:

使用priority函数判断输入的运算符的优先级,使用str字符数组储存输入的字符串,使用stack数组储存运算符,将str数组遍历,按照转化规则进行运算。

实现细节(代码):

#include<bits/stdc++.h>
using namespace std; 
int priority(char a)  // 判断运算符优先级
{
	switch(a)
	{
		case '(': return -1; break;
		case '+': return  1; break;
		case '-': return  1; break;
		case '*': return  2; break;
		case '/': return  2; break;
        default: return 0;
	}
}
 
 
int main()
{
	// 输入中缀表达式
	char str[1100]; memset(str, 0, sizeof(str)); scanf("%s", str);
	str[strlen(str)] = ')';  // 在最后补一个‘)’
 
	// 存放运算符的栈
	int top = 1; char stack[1000]; memset(stack, 0, sizeof(stack));
	stack[0] = '(';  // 首位默认为‘(’
 
	for (int i = 0; str[i]; i++)
	{
		// 如果是数字,直接输出
		if('0' <= str[i] && str[i] <= '9') printf("%c", str[i]);
		else
		{
			int operator_level = priority(str[i]);  // 计算此运算符的优先级
 
			// 如果是右括号‘)’,输出栈的内容到左括号为止
			if (str[i] == ')'){
				while (stack[top-1] != '(')	{printf("%c", stack[--top]);}
				top--;
			}
 
			// 如果是左括号‘(’,直接存入栈
			else if (str[i] == '(') stack[top++] = '(';
 
			else{
				// 对于其他的类型再做判断
                // 1:如果 当前运算符的优先级<=栈顶运算符的优先级 ——> 输出栈顶
				while (operator_level <= priority(stack[top - 1]))	{printf("%c", stack[--top]);}
                // 当运算符的优先级 > 栈顶运算符的优先级 ——> 把当前运算符存进栈
				stack[top++] = str[i];  
			}
		}
	}
	return 0;
} 

总结:

应当牢记栈的思想,出栈入栈是怎么样的,灵活使用栈和队列。

暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇