1. 首页
2. 数据结构
3. 本页

UVALive 4817 Calculator (表达式计算)

题意：~

思路：大数中缀表达式计算。。

import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.math.BigInteger;
import java.util.Scanner;
import java.util.StringTokenizer;
import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.InputStream;
import java.util.Stack;

public class Main {

    public static void main(String[] args) {
        //InputStream inputStream = System.in;
        //OutputStream outputStream = System.out;
        //InputReader in = new InputReader(inputStream);
        //PrintWriter out = new PrintWriter(outputStream);
        //Task solver = new Task();
        //solver.solve(1, in, out);
        //out.close();
        Scanner in = new Scanner(System.in);
        String str, mmp;
        while(in.hasNext()) {
            int c1 = 0, c2 = 0;
            str = "";
            while(true) {
                mmp = in.nextLine();
                for(int i = 0; i < mmp.length(); ++i) {
                    char cc = mmp.charAt(i);
                    if(cc == '(') c1++;
                    else if(cc == ')') c2++;
                }
                str += mmp;
                if(c1 == c2) break;
            }
            if(str.length() == 0) continue;
            Task solver = new Task();
            solver.togg(str);
        }
    }

    static class Task {
        public void togg(String str)
        {
            Stack s1 = new Stack();
            Stack s2 = new Stack();
            for (int i = 0; i < str.length(); ++i) {
                char c = str.charAt(i);
                if(c == ' ') continue;
                if(c >= '0' && c <= '9') {
                    BigInteger res = BigInteger.ZERO;
                    BigInteger cnt = BigInteger.valueOf(10);
                    int p = i;
                    boolean flag = true;
                    int cc = 0;
                    while(str.charAt(p) >= '0' && str.charAt(p) <= '9') {
                        res = res.multiply(cnt);
                        res = res.add(BigInteger.valueOf((int)str.charAt(p) - 48));
                        cc++;
                        if(p + 1 < str.length()) p++;
                        else {
                            flag = false;
                            break;
                        }
                    }
                    if(cc > 90) {
                        System.out.println("Error");
                        return;
                    }
                    s2.push(res);
                    if(flag) i = p - 1;
                    else i = str.length();
                } else if(c == '(') {
                    s1.push(c);
                } else if(c == ')') {
                    while(s1.peek().toString().charAt(0) != '(') {
                        s2.push(s1.peek());
                        s1.pop();
                    }
                    s1.pop();
                } else {
                    while(true) {
                        if(s1.empty() || s1.peek().toString().charAt(0) == '(') {
                            s1.push(c);
                            break;
                        }
                        char op = s1.peek().toString().charAt(0);
                        if((c == '*' || c == '/') && (op == '+' || op == '-')) {
                            s1.push(c);
                            break;
                        }
                        s2.push(s1.peek());
                        s1.pop();
                    }
                }
            }
            while(!s1.empty()) {
                s2.push(s1.peek());
                s1.pop();
            }
            while(!s2.empty()) {
                s1.push(s2.peek());
                s2.pop();
            }
            while(!s1.empty()) {
                char op = s1.peek().toString().charAt(0);
                if(op >= '0' && op <= '9') {
                    s2.push(s1.peek());
                    s1.pop();
                } else {
                    if(s2.empty()) {
                        System.out.println("Error");
                        return;
                    }
                    BigInteger a = new BigInteger(String.valueOf(s2.peek().toString()));
                    s2.pop();
                    if(s2.empty()) {
                        System.out.println("Error");
                        return;
                    }
                    BigInteger b = new BigInteger(String.valueOf(s2.peek().toString()));
                    s2.pop();
                    BigInteger c;
                    if(op == '+') {
                        c = b.add(a);
                    } else if(op == '-') {
                        c = b.subtract(a);
                    } else if(op == '*') {
                        c = b.multiply(a);
                    } else {
                        if(a.compareTo(BigInteger.ZERO) == 0) {
                            System.out.println("Error");
                            return;
                        }
                        c = b.divide(a);
                    }
                    if(c.compareTo(BigInteger.ZERO) < 0) {
                        System.out.println("Error");
                        return;
                    }
                    BigInteger d = c;
                    int cnt = 0;
                    while(d.compareTo(BigInteger.ZERO) != 0) {
                        d = d.divide(BigInteger.valueOf(10));
                        cnt++;
                    }
                    if(cnt > 90) {
                        System.out.println("Error");
                        return;
                    }
                    s2.push(c);
                    s1.pop();
                }
            }
            if(s2.empty()) {
                System.out.println("Error");
                return;
            }
            BigInteger a = new BigInteger(String.valueOf(s2.peek().toString()));
            if(a.compareTo(BigInteger.ZERO) < 0) {
                System.out.println("Error");
                return;
            }
            int cnt = 0;
            BigInteger b = a;
            while(a.compareTo(BigInteger.ZERO) != 0) {
                a = a.divide(BigInteger.valueOf(10));
                cnt++;
            }
            if(cnt > 90) {
                System.out.println("Error");
                return;
            }
            System.out.println(b);
        }

        public void solve(int testNumber, InputReader in, PrintWriter out) {
        }
    }

    static class InputReader {
        public BufferedReader reader;
        public StringTokenizer tokenizer;

        public InputReader(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream), 32768);
            tokenizer = null;
        }

        public String next() {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }

    }
}