算术表达式的转换栈

2024-08-28 17:18

文章标签 转换表达式算术

本文主要是介绍算术表达式的转换栈，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目描述

小明在学习了数据结构之后，突然想起了以前没有解决的算术表达式转化成后缀式的问题，今天他想解决一下。

因为有了数据结构的基础小明很快就解出了这个问题，但是他突然想到怎么求出算术表达式的前缀式和中缀式呢？小明很困惑。聪明的你帮他解决吧。

输入

输入一算术表达式，以\'#\'字符作为结束标志。（数据保证无空格,只有一组输入）

输出

输出该表达式转换所得到的前缀式中缀式后缀式。分三行输出，顺序是前缀式中缀式后缀式。

示例输入

a*b+(c-d/e)*f#

示例输出

+*ab*-c/def
a*b+c-d/e*f
ab*cde/-f*+

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<stack>
using namespace std;
int bijiao(char a,char b)
{if(a=='*'||a=='/')return 1;else if((a=='+'||a=='-')&&(b=='+'||b=='-'))return 1;elsereturn 0;
}
int bijiao2(char a,char b)
{if((a=='*'||a=='/')&&(b=='+'||b=='-'))return 1;elsereturn 0;
}
int main()
{char str[200000],str2[200000],str3[200000];stack<char>q;scanf("%s",str);int len=strlen(str);int k=0;int j=len-1;while(str[j]!='#')j--;for(int i=j-1; i>=0; i--){str2[k++]=str[i];}str2[k++]='#';str2[k]='\0';len=strlen(str2);j=0;for(int i=0;i<len; i++){if(str2[i]>='a'&&str2[i]<='z'){str3[j++]=str2[i];}else if(str2[i]=='*'||str2[i]=='/'||str2[i]=='+'||str2[i]=='-'){if(q.empty()||q.top()==')')q.push(str2[i]);else{if (bijiao2(q.top(),str2[i])){str3[j++]=q.top();q.pop();q.push(str2[i]);}else{q.push(str2[i]);}}}else  if(str2[i]==')'||str2[i]=='('){if(str2[i]==')')q.push(str2[i]);else if(str2[i]=='('){while(q.top()!=')'){str3[j++]=q.top();q.pop();}if(q.top()==')')q.pop();}}else{while(!q.empty()){str3[j++]=q.top();q.pop();}}if(str2[i]=='#')break;}for(int i=j-1; i>=0; i--)cout<<str3[i];cout<<endl;for(int i=0; str[i]!='#'; i++){if(str[i]!='('&&str[i]!=')')cout<<str[i];}cout<<endl;len=strlen(str);while(!q.empty())q.pop();for(int i=0; i<len; i++){if(str[i]>='a'&&str[i]<='z'){cout<<str[i];}else if(str[i]=='*'||str[i]=='/'||str[i]=='+'||str[i]=='-'){if(q.empty()||q.top()=='(')q.push(str[i]);else{if (bijiao(q.top(),str[i])){cout<<q.top();q.pop();q.push(str[i]);}else{q.push(str[i]);}}}else  if(str[i]==')'||str[i]=='('){if(str[i]=='(')q.push(str[i]);else if(str[i]==')'){while(!q.empty()&&q.top()!='('){cout<<q.top();q.pop();}if(q.top()=='(')q.pop();}}else{while(!q.empty()){cout<<q.top();q.pop();}}if(str[i]=='#')break;}cout<<endl;return 0;
}

唉！！坑爹啊，我竟然忘了在前缀的时候需要重新定义比较错了n遍，orz

这篇关于算术表达式的转换栈的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！