表达式转换——中缀表达式转换为后缀表达式

表达式转换

算术表达式有前缀表示法、中缀表示法和后缀表示法等形式。日常使用的算术表达式是采用中缀表示法&＃xff0c;即二元运算符位于两个运算数中间。请设计程序将中缀表达式转换为后缀表达式。

输入格式:
输入在一行中给出不含空格的中缀表达式&＃xff0c;可包含&＃43;、-、*、\以及左右括号()&＃xff0c;表达式不超过20个字符。

输出格式:
在一行中输出转换后的后缀表达式&＃xff0c;要求不同对象&＃xff08;运算数、运算符号&＃xff09;之间以空格分隔&＃xff0c;但结尾不得有多余空格。

输入样例:

2&＃43;3*(7-4)&＃43;8/4

输出样例:

2 3 7 4 - * &＃43; 8 4 / &＃43;

知识点&＃xff1a;将中缀表达式转化为后缀表达式&＃xff1a;
两种情况&＃xff1a;
&＃xff08;1&＃xff09;没有括号的中缀表达式转化为后缀表达式&＃xff1a;

&＃xff08;2&＃xff09;带有括号的中缀表达式转化为后缀表达式&＃xff1a;

分析&＃xff1a;本题是带有括号的中缀表达式&＃xff0c;需要利用第二种方式实现&＃xff0c;模拟过程我会在代码上详解
这里说一下这道题的细节问题&＃xff1a;
中缀表达式转换为后缀表达式&＃xff1a;对于本题而言&＃xff0c;细节过多&＃xff0c;在完成表达式转换的基础上
1.需要控制空格&＃xff0c;首尾不能出现空格
2.需要判断一位以上的数字之间不能有空格
3.需要判断小数的情况&＃xff0c;注意之间不能有空格
4.需要判断镶嵌括号的情况&＃xff0c;容易出现格式错误
例如&＃xff1a;当一开始就输入多个空格会使首位出现空格
5.需要判断正负号
&＃xff08;1&＃xff09;对于正号&＃xff0c;当出现在第一位时需直接特判&＃xff08;在第一位无需加括号&＃xff09;
未在第一位出现正号一定会在括号内&＃xff0c;而且输出时正号要省略
&＃xff08;2&＃xff09;对于负号&＃xff0c;当出现在第一位时需要直接特判&＃xff08;在第一位出现无需加括号&＃xff09;
未在第一位出现负号一定会在括号内&＃xff0c;需要输出负号
&＃xff08;3&＃xff09;注意控制好空格&＃xff0c;防止格式错误

下面是代码&＃xff1a;


#include
#include
#include
#include
#include
using namespace std;
const int M&＃61;1010;
char str[M],st[M],c;
stack<char> q;
int main()
{int i,j,k&＃61;0,l,m,n,f&＃61;0,t&＃61;0,ff&＃61;0;cin.getline(str,110);l&＃61;strlen(str);for(i&＃61;0; i<l; i&＃43;&＃43;){if(str[i]>&＃61;&＃39;0&＃39;&&str[i]<&＃61;&＃39;9&＃39;)///为数字时输出{t&＃61;1;///标记已经出现过数字///解决当有镶嵌括号时的格式问题if(ff&＃61;&＃61;0)///特判当刚开始有镶嵌括号时防止f&＃61;1对格式的影响{printf("%c",str[i]);ff&＃61;1;f&＃61;0;continue;}///解决超过一位数的问题if(f&＃61;&＃61;0)///遇到数字并且前一个也是数字或&＃39;.&＃39;输出printf("%c",str[i]);else ///f&＃61;1时遇到数字加空格输出&＃xff0c;并使f&＃61;0{printf(" %c",str[i]);f&＃61;0;}}///解决小数问题else if(str[i]&＃61;&＃61;&＃39;.&＃39;)///遇到点说明为小数直接输出{printf("%c",str[i]);}///解决第一位为正数带&＃39;&＃43;&＃39;的问题else if(i&＃61;&＃61;0&&str[i]&＃61;&＃61;&＃39;&＃43;&＃39;){printf("%c",str[i]);}///解决第一位为正数带&＃39;-&＃39;的问题else if(i&＃61;&＃61;0&&str[i]&＃61;&＃61;&＃39;-&＃39;){printf("%c",str[i]);}///解决非第一位为正数带&＃39;-&＃39;的问题else if(str[i]&＃61;&＃61;&＃39;(&＃39;&&str[i&＃43;1]&＃61;&＃61;&＃39;-&＃39;){///输出符号if(t&＃61;&＃61;1)///若已经出现数字&＃xff0c;加符号时需在前面加空格printf(" %c",str[i&＃43;1]);elseprintf("%c",str[i&＃43;1]);q.push(str[i]);///将括号入栈f&＃61;0;///输出数字无需加空格i&＃43;&＃43;;///跳过这个&＃39;-&＃39;}///解决非第一位为正数带&＃39;&＃43;&＃39;的问题else if(str[i]&＃61;&＃61;&＃39;(&＃39;&&str[i&＃43;1]&＃61;&＃61;&＃39;&＃43;&＃39;){///带正号的数字的正号可以约去q.push(str[i]);///将括号入栈f&＃61;1;///输入数字时需要加空格i&＃43;&＃43;;///跳过&＃39;&＃43;&＃39;}///当遇见左括号else if(str[i]&＃61;&＃61;&＃39;(&＃39;){q.push(str[i]);///放入栈中f&＃61;1;}///遇见右括号else if(str[i]&＃61;&＃61;&＃39;)&＃39;){///输出左括号到右括号之间的符号while(q.top()!&＃61;&＃39;(&＃39;){printf(" %c",q.top());f&＃61;1;///当输入数字时需加空格q.pop();///将输出的字符出栈}//printf("%c\n",q.top());q.pop();///将左括号出栈}else{///当栈为空或者栈顶元素为左括号if(q.size()&＃61;&＃61;0||q.top()&＃61;&＃61;&＃39;(&＃39;){f&＃61;1;///输入数字时需要加空格q.push(str[i]);///将符号放入栈中}///当需要入栈的符号优先级大于栈顶符号优先级else if((str[i]&＃61;&＃61;&＃39;*&＃39;||str[i]&＃61;&＃61;&＃39;/&＃39;)&&(q.top()&＃61;&＃61;&＃39;&＃43;&＃39;||q.top()&＃61;&＃61;&＃39;-&＃39;)){f&＃61;1;///输入数字时需加括号q.push(str[i]);///将符号入栈}///入栈的符号优先级小于或等于栈顶符号优先级///栈中元素不为空且栈顶元素不是左括号else{///当栈顶元素为&＃39;*&＃39;或&＃39;/&＃39;if(q.top()&＃61;&＃61;&＃39;*&＃39;||q.top()&＃61;&＃61;&＃39;/&＃39;){f&＃61;1;///输入数字需加空格printf(" %c",q.top());///加空格输出栈顶元素q.pop();///将栈顶元素出栈///出栈完看栈中元素是否为空///此时四种情况///&＃xff08;1&＃xff09;栈中元素为0///&＃xff08;2&＃xff09;栈顶元素为&＃39;(&＃39;///&＃xff08;3&＃xff09;栈底元素为&＃39;&＃43;&＃39;或&＃39;-&＃39;&＃xff0c;输入符号为&＃39;*&＃39;或&＃39;/&＃39;///&＃xff08;4&＃xff09;栈底元素为&＃39;&＃43;&＃39;或&＃39;-&＃39;&＃xff0c;输入符号为&＃39;&＃43;&＃39;或&＃39;-&＃39;///情况一和情况二if(q.size()&＃61;&＃61;0||q.top()&＃61;&＃61;&＃39;(&＃39;){f&＃61;1;///输出数字时需加空格q.push(str[i]);///将符号放入栈中}///情况三else if(str[i]&＃61;&＃61;&＃39;*&＃39;||str[i]&＃61;&＃61;&＃39;/&＃39;){f&＃61;1;///输出数字时需加空格q.push(str[i]);///直接将符号入栈}///情况四else if(str[i]&＃61;&＃61;&＃39;&＃43;&＃39;||str[i]&＃61;&＃61;&＃39;-&＃39;){f&＃61;1;///输出数字时需加空格printf(" %c",q.top());///将栈顶元素加空格输出q.pop();///栈顶元素出栈q.push(str[i]);///将符号放入栈中}}///当栈顶元素为&＃39;&＃43;&＃39;或&＃39;-&＃39;else if(q.top()&＃61;&＃61;&＃39;&＃43;&＃39;||q.top()&＃61;&＃61;&＃39;-&＃39;){///两种情况///&＃xff08;1&＃xff09;入栈符号为&＃39;*&＃39;或&＃39;/&＃39;///&＃xff08;2&＃xff09;入栈符号为&＃39;&＃43;&＃39;或&＃39;-&＃39;///情况一if(str[i]&＃61;&＃61;&＃39;*&＃39;||str[i]&＃61;&＃61;&＃39;/&＃39;){f&＃61;1;///输出数字时需加空格q.push(str[i]);///将符号放入栈中}else if(str[i]&＃61;&＃61;&＃39;&＃43;&＃39;||str[i]&＃61;&＃61;&＃39;-&＃39;){f&＃61;1;///输出数字时需加空格printf(" %c",q.top());///输出栈顶元素q.pop();///栈顶元素出栈q.push(str[i]);///将符号放入栈中}}}}}///当栈中符号未完全出栈while(q.size()!&＃61;0){printf(" %c",q.top());///将栈中符号依次输出q.pop();///依次出栈}printf("\n");return 0;
}