算术表达式的转换（栈与队列）

算术表达式的转换

Time Limit: 1000 ms Memory Limit: 65536 KiB

Submit Statistic Discuss

Problem Description

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

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

Input

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

Output

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

Sample Input

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

Sample Output

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

说明：栈的存放并不是一下子把所有的东西都放进去，而是边操作边存放的 
1.对于中缀表达式向前缀表达式的转换：需要两个栈，一个栈存储字母，另一个栈存储运算符；并且前缀表达式是从右向左开始的（后缀表达式是从左向右开始的）当遇到字母的时候，进栈1，当遇到运算符的时候，进栈2，这时候进栈2是有条件的：1.如果当前的运算符是加减，而栈2的top是乘除，这时候要把栈2的top元素转移到栈1中（注意这时候没有相等的情况，和后缀表达式不一样，后缀表达式还有两种情况是当前的元素是加减，栈顶的元素也是加减；当前的元素是乘除，栈顶的元素也是乘除）然后当前的元素进栈2；2.当当前的元素是左括号的时候要去找右括号，除了这两个括号之外，把他们之间的元素都放到栈1里面（后缀表达式是当前是左括号，去找右括号，并且左右括号之间的元素是输出，而不是进入另一个栈）；3.其他的情况入栈2就行了；之后把栈2里面的元素都给清到栈1里面，最后把栈1的元素都输出即可； 
中缀表达式向后缀表达式转换：只需要一个栈，存放运算符；当遇到字母就输出，当遇到运算符就进栈，这里的进栈是有条件的：1.如果当前的元素是加减，栈顶的元素是乘除，栈顶元素先输出，当前元素入栈；或者当前的元素是加减，栈顶的元素也是加减；或者当前的元素是乘除，栈顶的元素也是乘除；同样的操作；2.如果当前的元素是右括号，就要去栈里面找左括号 ，并且输出除了左右括号之外的所有的运算符；3.其他的情况就是入栈了；最后把栈里面的所有元素都输出； 
2.对于前缀表达式和后缀表达式的运算：后缀表达式：需要一个栈存放操作数，遇到一个运算符就要对栈顶元素和栈次元素进行操作，注意这里的操作是栈次元素对栈顶元素进行加减乘除，之后top要退一位，最后输出栈顶的值即可； 
前缀表达式：是从右往左扫描操作数入栈，操作的时候是栈顶元素对栈次元素进行加减乘除的运算；最后输出栈顶元素即可；

原文：https://blog.csdn.net/BHliuhan/article/details/81179875 

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
char z1[200],z2[200],s[200],a[200];
int main()
{
    scanf("%s",s);
    int len=strlen(s);
    int top=0,top1=0,top2=0;
    for(int i=len-2; i>=0; i--)
    {
        if(s[i]>='a'&&s[i]<='z')
        {
            z1[++top1]=s[i];
        }
        else if((s[i]=='+'||s[i]=='-')&&(z2[top2]=='*'||z2[top2]=='/'))//一定要注意这个地方，不能图省事，直接写成s[i]=='+'||'-'，这样是错误的

        {
            z1[++top1]=z2[top2];
            z2[top2]=s[i];
        }
        else if(s[i]=='(')
        {
            while(z2[top2]!=')')
            {
                z1[++top1]=z2[top2--];
            }
            top2--;
        }
        else
        {
            z2[++top2]=s[i];
        }
    }
    while(top2!=0)
    {
        z1[++top1]=z2[top2--];
    }
    while(top1!=0)
    {
        printf("%c",z1[top1--]);
    }
    printf("\n");//前缀表达式的转换
    len=strlen(s);
    for(int i=0; i<len-1;)
    {
        if(s[i]==')'||s[i]=='(')
        {
            i++;
        }
        else
        {
            printf("%c",s[i]);
            i++;
        }
    }
    printf("\n");//中缀表达式的转换
    len=strlen(s);
    for(int i=0; i<len-1; i++)
    {
        if(s[i]>='a'&&s[i]<='z')
        {
            printf("%c",s[i]);
        }
        else
        {
            if(((s[i]=='+'||s[i]=='-')&&(a[top]=='*'||a[top]=='/'))||
              ((s[i]=='+'||s[i]=='-')&&(a[top]=='+'||a[top]=='-'))||
              ((s[i]=='*'||s[i]=='/')&&(a[top]=='*'||a[top]=='/')))
            {
                printf("%c",a[top]);
                a[top]=s[i];
            }
            else if(s[i]==')')
            {
                while(a[top]!='(')
                {
                    printf("%c",a[top--]);
                }
                top--;
            }
            else
            {
                a[++top]=s[i];
            }
        }
    }
    while(top!=0)
    {
        printf("%c",a[top--]);
    }
    printf("\n");//后缀表达式的转换
    return 0;
}