7-21 求前缀表达式的值（二叉树）

秒速五厘米 2022-04-22 08:50 165阅读 0赞

算术表达式有前缀表示法、中缀表示法和后缀表示法等形式。前缀表达式指二元运算符位于两个运算数之前，例如2+3\*(7-4)+8/4的前缀表达式是：+ + 2 \* 3 - 7 4 / 8 4。请设计程序计算前缀表达式的结果值。

## 输入格式: ##

输入在一行内给出不超过30个字符的前缀表达式，只包含+、-、\*、\\以及运算数，不同对象（运算数、运算符号）之间以空格分隔。

## 输出格式: ##

输出前缀表达式的运算结果，保留小数点后1位，或错误信息ERROR。

## 输入样例: ##

+ + 2 * 3 - 7 4 / 8 4

## 输出样例: ##

13.0

用二叉树的思路很好想，就是数据处理有点麻烦，我的代码虽然PTA的测试样例通过了，但我估计还有其他的样例有一些错误，，下次还是老老实实的用栈模拟吧。。

#include <bits/stdc++.h>
    using namespace std;
    
    typedef char ElementType;
    typedef struct TNode *BTree;
    struct TNode{
        
        BTree Left;
        BTree Right;
        double num;
    };
    int f=0,k=0;
    string s;
    double BuildTree(BTree t){
        
        t=(BTree)malloc(sizeof(BTree));
        char c;
        if(k>=s.length()){
        
            f=1;
            return 0;
        }
        c=s[k++];
        if(c-'0'>=0&&c-'0'<=9){
        
            double sum;
            sum=c-'0';
            int isdecimals=0,cnt=10;
            while(1){
        
                c=s[k++];
                if(c=='.'){
        
                    isdecimals=1;
                    continue;
                }
                if(c<'0')break;
                if(!isdecimals)sum=sum*10+c-'0';
                else {
        
                    sum=sum+(c-'0')*1.0/cnt;
                    cnt*=10;
                }
            }
            return sum;
        }
        else if(c<'0'&&s[k]-'0'>=0&&s[k]-'0'<=9){
        
            double sum=0;
            char q=c;
            int isdecimals=0,cnt=10;
            while(1){
        
                c=s[k++];
                if(c=='.'){
        
                    isdecimals=1;
                    continue;
                }
                if(c<'0')break;
                if(!isdecimals)sum=sum*10+c-'0';
                else {
        
                    sum=sum+(c-'0')*1.0/cnt;
                    cnt*=10;
                }
            }
            if(q=='-')return -sum;
            else return sum;
        }
        k++;
        double a=BuildTree(t->Left);
        double b=BuildTree(t->Right);
        if(c=='+'){
        
            t->num=a+b;
        }
        else if(c=='-'){
        
            t->num=a-b;
        }
        else if(c=='*'){
        
            t->num=a*b;
        }
        else if(c=='/'){
        
            if(b==0){
        
                f=1;
                return 0;
            }
            t->num=a/b;
        }
        return t->num;
    }
    int main(){
        
        BTree t;
        getline(cin,s);
        double sum=BuildTree(t);
        if(f==1)cout<<"ERROR"<<endl;
        else printf("%.1lf",sum);
    }