224.基本计算器

链接：224.基本计算器
难度：Hard
标签：栈、递归、数学、字符串
简介：实现一个基本的计算器来计算一个简单的字符串表达式的值字符串表达式可以包含左括号 ( ，右括号 )，加号 + ，减号 -，非负整数和空。

题解 1 - java

• 编辑时间：2020-02-16
• 执行用时：145ms
• 内存消耗：76.4MB
• 编程语言：java
• 解法介绍：先把字符串转换为后缀表达式，然后再利用栈计算。

class Solution {
    public int calculate(String s) {
		Stack<String> stack1 = new Stack<String>();
		Stack<String> stack2 = new Stack<String>();
		int len = s.length();
		String tem = "";
		for (int i = 0; i < len; i++) {
//			System.out.println("tem:" + tem);
//			System.out.println("stack1:" + stack1);
//			System.out.println("stack2:" + stack2);
			String ch = s.charAt(i) + "";
			if (ch.compareTo(" ") == 0)
				continue;
			if (ch.compareTo("+") == 0 || ch.compareTo("-") == 0 || ch.compareTo("(") == 0) {
				stack1.push(ch);
				continue;
			}
			if (ch.compareTo(")") == 0) {
				stack1.pop();
				if (!stack1.isEmpty())
					stack2.push(stack1.pop());
				continue;
			}
			if (i != len - 1 && s.charAt(i + 1) >= 48 && s.charAt(i) <= 57) {
//				System.out.println(1);
				tem += ch;
				continue;
			} else {
//				System.out.println(2);
				if(tem.compareTo("")!=0) {
					ch = tem+ch;
					tem = "";
				}
			}
			stack2.push(ch);
			if (stack1.isEmpty())
				continue;
			if (stack1.peek().compareTo("+") == 0 || stack1.peek().compareTo("-") == 0) {
				stack2.push(stack1.pop());
			}
		}
//		System.out.println(stack2);
		Deque<String> tokens = new LinkedList<String>();
		while (!stack2.isEmpty()) {
			tokens.offerFirst(stack2.pop() + "");
		}
//		System.out.println(tokens);
		return evalRPN(tokens);
//		return evalRPN("");
	}
	public int evalRPN(Deque<String> tokens) {
		Stack<String> stack = new Stack<String>();
		int a, b;
		for (String s : tokens) {
			switch (s) {
			case "+":
				a = Integer.parseInt(stack.pop());
				b = Integer.parseInt(stack.pop());
				stack.push((a + b) + "");
				break;
			case "-":
				a = Integer.parseInt(stack.pop());
				b = Integer.parseInt(stack.pop());
				stack.push((b - a) + "");
				break;
			case "*":
				a = Integer.parseInt(stack.pop());
				b = Integer.parseInt(stack.pop());
				stack.push((a * b) + "");
				break;
			case "/":
				a = Integer.parseInt(stack.pop());
				b = Integer.parseInt(stack.pop());
				stack.push((b / a) + "");
				break;
			default:
				stack.push(s);
				break;
			}
		}
		return Integer.parseInt(stack.pop());
	}
}

题解 2 - typescript

• 编辑时间：2021-03-10
• 执行用时：148ms
• 内存消耗：44.9MB
• 编程语言：typescript
• 解法介绍：利用栈依次计算，并转换减法为加法。

const numReg = /\-?\d+/;
const opReg = /\+|\-/;
const squareReg = /\(|\)/;
const opMap: Record<string, (num1: number, num2: number) => number> = {
  '+': (num1, num2) => num1 + num2,
  '-': (num1, num2) => num1 - num2,
  '*': (num1, num2) => num1 * num2,
  '/': (num1, num2) => num1 / num2,
};
const emptyReg = / /g;
function calculate(s: string): number {
  s = s.replace(emptyReg, '');
  const stack: string[] = [];
  const peek = () => stack[stack.length - 1];
  if (s[0] === '-') s = '0' + s;
  const len = s.length;
  for (let i = 0; i < len; i++) {
    let c = s[i];
    if (opReg.test(c) || c === '(') {
      stack.push(c);
    } else if (c === ')') {
      let c = 0;
      let str = '';
      while (peek() !== '(') {
        str = stack.pop()! + str;
        cpp;
      }
      stack.pop();
      str = (c === 1 ? str : calculate(str)) + '';
      if (peek() === '-') {
        stack[stack.length - 1] = '+';
        str = str.startsWith('-') ? str.substring(1) : '-' + str;
      }
      stack.push(str);
    } else {
      while (i < len - 1 && numReg.test(s[i + 1])) {
        c += s[++i];
      }
      if (peek() === '-') {
        c = stack.pop()! + c;
        if (numReg.test(peek())) stack.push('+');
      }
      const top = peek();
      if (opReg.test(top)) {
        const op = stack.pop()!;
        const num1 = stack.pop()!;
        stack.push(opMap[op](Number(num1), Number(c)) + '');
      } else {
        stack.push(c);
      }
    }
  }
  return stack.length === 1 ? Number(stack[0]) : calculate(stack.join(''));
}