Why TLE when I use infix to postfix to calculate?


  • 1
    L
    int calculate(string s) {
        return inf2postf(s);
    }
    int inf2postf(string s)
    {
        vector<string> v;
        stack<string> str;
        for(int i = 0; i < s.length(); i++)
        {
            if(s[i] >= '0' && s[i] <= '9')
            {
                int num = 0;
                while(s[i] >= '0' && i < s.length())
                    num = num * 10 + s[i] - '0';
                v.push_back(to_string(num));
            }
            else if(s[i] == '+' || s[i] == '-')
            {
                while(!str.empty())
                {
                    v.push_back(str.top());
                    str.pop();
                }
                string s1 = "";
                s1.push_back(s[i]);
                str.push(s1);
            }
            else if(s[i] == '*' || s[i] == '/')
            {
                while(!str.empty() && str.top() != "+" && str.top() != "-")
                {
                    v.push_back(str.top());
                    str.pop();
                }
                string s2 = "";
                s2.push_back(s[i]);
                str.push(s2);
            }
        }
        while(!str.empty())
        {
            v.push_back(str.top());
            str.pop();
        }
        
        stack<int> si;
        for(int i = 0; i < v.size(); i++)
        {
            if(v[i][0] >= '0')
            {
                si.push(stoi(v[i]));
            }
            else
            {
                int n1 = si.top(); si.pop();
                int n2 = si.top(); si.pop();
                switch(v[i][0])
                {
                    case '+':
                        si.push(n2 + n1); break;
                    case '-':
                        si.push(n2 - n1); break;
                    case '*':
                        si.push(n2 * n1); break;
                    case '/':
                        si.push(n2 / n1); break;
                }
            }
        }
        return si.top();
    }

  • 0
    A

    I have the same problem.

    public class Solution {
         public int calculate(String s) {
            String postFix = getPostFix(s);
            // System.out.println(postFix);
            return evaluatePostFix(postFix);
        }
    
        String getPostFix(String s) {
            String result = new String();
            Stack<Character> stack = new Stack<Character>();
            for (int i = 0; i <= s.length() - 1; i++) {
                char c = s.charAt(i);
                // System.out.println(c);
                if (isNum(c) == true) {
                    result = result + Character.toString(c);
                } else if (c != ' ') {
                    result = result + " ";
                    if (stack.empty() == false) {
                        while (stack.empty() == false &&
                               getPrecedence(stack.peek()) > getPrecedence(c)) {
                            result = result + Character.toString(stack.pop());
                        }
                    }
                    stack.push(c);
                } else {
                    result = result + " ";
                }
            }
            // System.out.println(stack.size());
            while (stack.empty() == false) {
                result = result + Character.toString(stack.pop());
            }
    
            return result;
        }
    
        int getPrecedence(char c) {
            switch (c) {
            case '+':
            case '-':
                return 1;
            case '/':
            case '*':
                return 2;
            }
            return -1;
        }
    
        boolean isNum(char c) {
            int i = (int) c - 48;
            return (i >= 0 && i <= 9);
        }
        
        int evaluatePostFix(String s) {
            Stack<Integer> stack = new Stack<Integer>();
    
            for (int i = 0; i <= s.length() - 1; i++) {
                char c = s.charAt(i);
                if (isNum(c) == true) {
                    int num = 0;
                    while (i <= s.length() - 1 && isNum(s.charAt(i)) == true) {
                        int n = (int) s.charAt(i) - 48;
                        num = num * 10 + n;
                        i++;
                    }
                    stack.push(num);
                    //System.out.println("Pushing to stack: " + num);
                    i--;
                } else if (c != ' ') {
                    Integer num1 = stack.pop();
                    Integer num2 = stack.pop();
                    Integer result = apply(num2, num1, c);
                    stack.push(result);
                }
            }
    
            return stack.pop();
        }
    
        int apply(int num1, int num2, char c) {
            // System.out.println("Applying " + num1 + " " + num2 + " to " + c);
            switch (c) {
            case '+':
                return num1 + num2;
            case '-':
                return num1 - num2;
            case '*':
                return num1 * num2;
            case '/':
                return num2 != 0 ? num1 / num2 : 0;
            default:
                return 0;
            }
        }
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.