美文网首页
BM49 表达式求值

BM49 表达式求值

作者: help_youself | 来源:发表于2022-07-05 17:13 被阅读0次
    #include <iostream>
    #include <string>
    #include <stack>
    using namespace std;
    static inline int GetPrecendence(const char &c){
        switch(c){
        case '+':
        case '-':
            return 10;
        case '*':
        case '/':
            return 20;
        default:
            return 0;
        }
    }
    static inline bool IsNum(const char &c){
        return c>='0'&&c<='9';
    }
    static inline bool IsOp(const char &c){
        bool ret=false;
        if(c=='+'||c=='-'||c=='*'||c=='/'){
            ret=true;
        }
        return ret;
    }
    static inline bool IsTerminator(const char &c){
        bool ret=false;
        if(IsOp(c)||'('==c||')'==c){
            ret=true;
           }
        return ret;
    }
    static inline int Cal(const int &a,const int&b,const char& op){
        std::cout<<a<<" "<<b<<" "<<op<<std::endl;
        switch(op){
        case '+':
            return a+b;
        case '-':
            return a-b;
        case '*':
            return a*b;
        case '/':
            return a/b;
        default:
            return 0;
        }
    }
    class Solution {
    public:
        int solve(string s) {
            // write code here
            int n=s.size();
            int i=0;
            int val=0;
            bool num_flag=false;
            while(i<n){
                if(IsNum(s[i])){
                    val=val*10+s[i]-'0';
                    num_flag=true;
                }
                if(i==n-1||IsTerminator(s[i])){
                    if(num_flag){
                        std::cout<<val<<std::endl;
                        nums.push(val);
                    }
                    val=0;
                    num_flag=false;
                }
                if('('==s[i]){
                    ops.push(s[i]);
                   }else if(')'==s[i]){
                        while('('!=ops.top()){
                            int r=0;
                            int right=nums.top();
                            nums.pop();
                            char op=ops.top();
                            ops.pop();
                            if(IsOp(op)){
                                int left=nums.top();
                                nums.pop();
                                r=Cal(left,right,op);
                            }else{
                                r=right;
                            }
                            nums.push(r);
                        }
                        ops.pop();
                   }else if(IsOp(s[i])){
                        if(ops.empty()||'('==s[i]){
                            ops.push(s[i]);
                        }else if(IsOp(ops.top())&&GetPrecendence(ops.top())>=GetPrecendence(s[i])){
                            int right=nums.top();
                            nums.pop();
                            int left=nums.top();
                            nums.pop();
                            char op=ops.top();
                            ops.pop();
                            int r=Cal(left,right,op);
                            nums.push(r);
                            ops.push(s[i]);
                        }else{
                            ops.push(s[i]);
                        }
                   }
                i++;
            }
            while(!ops.empty()){
                int right=nums.top();
                nums.pop();
                int left=nums.top();
                nums.pop();
                char op=ops.top();
                ops.pop();
                int r=Cal(left,right,op);
                nums.push(r);
            }
            int r=0;
            r=nums.top();
            nums.pop();
            return r;
    }
    private:
        std::stack<char> ops;
        std::stack<int> nums;
    };
    int main(){
        std::string expression="1 2 +2 + (2+2+1*2)*3";
        Solution so;
        int r=so.solve(expression);
        std::cout<<r<<std::endl;
        return 0;
    }
    

    [1] BM49 表达式求值-中等

    相关文章

      网友评论

          本文标题:BM49 表达式求值

          本文链接:https://www.haomeiwen.com/subject/crisbrtx.html