Given a string STR, STR is an arithmetic expression containing four operations and parentheses (), [], {}. Ask to return the calculation results.

STR =”(3+1)*4/2″, return 8.

【 典 型 范 例 2 】 We should replace the braces with parentheses.

  1. Recursive processing of expressions in parentheses;
  2. Iterating through the character array, checking the string at the top of the stack for each complete number; (1) If the top of the stack is * or /, the stack can be calculated first; (2) If it is + or -, push it to the stack.
  3. After iterating through the character array, the only expressions left on the stack are + and -. Calculation can start from the top of the stack out of the stack, after the symbol of the number out of the stack; You can also think of a Deque as a two-ended queue, with the first queue coming out, and the symbol of the number going out first.

To summarize: recursive resolution handles parentheses; The multiplication and division are calculated when the stack is pushed, and the addition and subtraction are calculated after traversal, thus solving the symbol priority problem.

[code]

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            String line = sc.nextLine();
            line = line.replace("["."(");
            line = line.replace("]".")");
            line = line.replace("{"."(");
            line = line.replace("}".")");
            int n = value(line.toCharArray(), 0) [0]; System.out.println(n); }}private static int[] value(char[] chars, int i) {
        Deque<String> deque = new LinkedList<>();
        int pre = 0;
        int[] bra = null;
        while(i < chars.length && chars[i] ! =') ') {
        	// Take the full number
            if (chars[i] >= '0' && chars[i] <= '9') {
                pre  = pre * 10 + chars[i] - '0';
            } else if(chars[i] ! ='(') { // if +-*/ is encountered, it means the end of the number, put the number into the deque, and then put the symbol into the deque, reset the pre
                addNum(deque, pre);
                deque.offerLast(String.valueOf(chars[i]));
                pre = 0;
            } else { // enter recursion when '(' is encountered
                bra = value(chars, i + 1);
                pre = bra[0];
                i = bra[1];
            }
            i++;
        }
        addNum(deque, pre);
        return new int[]{getNum(deque), i};
    }
	
    // Put the number on the stack. First look at the top of the stack, if * or/then calculate, eliminate */; If +- is added to the stack
    private static void addNum(Deque<String> deque, int v) {
        if (deque.isEmpty()) {
            deque.addLast(String.valueOf(v));
            return;
        }
        String s = deque.peekLast();
        if (s.equals("*") || s.equals("/")) {
            deque.pollLast();
            Integer v2 = Integer.parseInt(deque.pollLast());
            v = s.equals("*")? v * v2 : v2 / v; } deque.addLast(String.valueOf(v)); }// Compute the result from the stack with only +-
    private static int getNum(Deque<String> deque) {
        boolean add = true;
        int res = 0;
        while(! deque.isEmpty()) { String s = deque.pollFirst();if (s.equals("+")) {
                add = true;
            } else if (s.equals("-")) {
                add = false;
            } else {
                intv = Integer.parseInt(s); res = add ? (res + v) : (res - v); }}returnres; }}Copy the code