题解 P1175 【表达式的转换】

Lynx · 2016-04-08 23:32:24 · 题解

大致思路：

1.中缀转后缀

2.按顺序求值

具体解释已由jiangyougogogo大神给出

贴一下c++代码

#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<stack>
using namespace std;
int top=0,k=0,num[100001];
char c[1000001],d[1000001];
bool b[1000001]={0};
stack<char>sym;
void push(char t)
{
    d[top]=t;
    top++;
    d[top]=' ';
    top++;
}
void psh(int t)
{
    k++;
    num[k]=t;
}
bool comp(char t)
{
    if(sym.empty()||sym.top()=='(')
        return 1;
    if(sym.top()=='^')
        return 0;
    if(t=='^')
        return 1;
    if(sym.top()=='*'||sym.top()=='/')
        return 0;
    if(t=='*'||t=='/')
        return 1;
    return 0;
}
void calc(char t)
{
    int x,y;
    char z;
    x=num[k];
    k--;
    y=num[k];
    k--;
    if(t=='+')
        psh(y+x);
    if(t=='-')
        psh(y-x);
    if(t=='*')
        psh(y*x);
    if(t=='/')
        psh(y/x);
    if(t=='^')
        psh(pow(y,x));
}
int main()
{
    gets(c);//。。。 
    for(int i=0;i<=strlen(c)-1;i++)
    {
        if(c[i]>='0'&&c[i]<='9')//如果是数字，直接存入d[] 
        {
            push(c[i]);
            continue;
        }
        if(c[i]=='(')//左括号优先级最大，直接进栈 
        {
            sym.push(c[i]);
            continue;
        }
        if(c[i]==')')//遇到右括号，退栈直到遇到左括号 
        {
            while(sym.top()!='(')
            {
                push(sym.top());
                sym.pop();
            }
            sym.pop();//左括号退栈 
            continue;
        }
        if(!comp(c[i]))//优先级小于等于，退栈 
        {
            while(!comp(c[i]))
            {
                push(sym.top());
                sym.pop();
            }
        }
        sym.push(c[i]);//符号进栈 
    }
    while(!sym.empty())
    {
        push(sym.top());
        sym.pop();
    }
    puts(d);//以上为中缀转后缀，d[]为后缀表达式 
    for(int i=0;i<=strlen(d)-1;i++)
    {
        if(d[i]>='0'&&d[i]<='9')//数字直接进栈 
        {
            psh(d[i]-'0');
            continue;
        }
        if(d[i]==' ')//空格跳过 
            continue;
        calc(d[i]);//计算 
        i++;//跳过该符号 
        for(int j=1;j<=k;j++)
            printf("%d ",num[j]);//先输出栈中数字 
        for(int j=i+1;j<=strlen(d)-1;j++)
            printf("%c",d[j]);//输出剩余表达式 
        printf("\n");
    }
    return 0;
}