Basic Calculator & Basic Calculator II

Basic Calculator

Description:

Implement a basic calculator to evaluate a simple expression string.

The expression string may contain open ( and closing parentheses ), the plus + or minus sign -, non-negative integers and empty spaces .

You may assume that the given expression is always valid.

Basic Calculator II

 

Description:

mplement a basic calculator to evaluate a simple expression string.

The expression string contains only non-negative integers, +, -, *, / operators and empty spaces . The integer division should truncate toward zero.

You may assume that the given expression is always valid.

Solution:

使用逆波兰表达式来解决这个问题，经典问题   逆波兰表达式

代码包含了加减乘除和括号

import java.util.*;

public class Solution {

	public int calculate(String s) {
		LinkedList<String> list = new LinkedList<String>();
		s = s + " ";
		toReversePolishNotation(s, list);
		System.out.println(list.toString());
		return calcReversePolishNotation(list);
	}

	void toReversePolishNotation(String s, LinkedList<String> list) {
		Stack<Character> operation = new Stack<Character>();
		operation.push('(');
		int preNum = 0;

		char ch;
		int currentLevel;
		for (int i = 0; i < s.length(); i++) {
			ch = s.charAt(i);
			if (ch >= '0' && ch <= '9') {
				preNum = preNum * 10 + ch - '0';
				if (s.charAt(i + 1) < '0' || s.charAt(i + 1) > '9') {
					list.add(preNum + "");
					preNum = 0;
				}
			} else {
				if (ch == '(') {
					operation.push(ch);
				} else if (ch == ')') {
					char tempC;
					while (!operation.isEmpty()) {
						tempC = operation.pop();
						if (tempC == '(')
							break;
						list.add(tempC + "");
					}
				} else if (ch != ' ') {
					currentLevel = getLevel(ch);

					char tempC;
					while (!operation.isEmpty()) {
						tempC = operation.peek();
						if (getLevel(tempC) < currentLevel)
							break;
						operation.pop();
						list.add(tempC + "");
					}
					operation.push(ch);
				}
			}
		}

		char tempC;
		while (operation.size() > 1) {
			tempC = operation.pop();
			list.add(tempC + "");
		}

		return;
	}

	int getLevel(char ch) {
		if (ch == '(')
			return 0;
		if (ch == '+')
			return 1;
		if (ch == '-')
			return 1;
		if (ch == '*')
			return 2;
		if (ch == '/')
			return 2;
		return 0;
	}

	int calcReversePolishNotation(LinkedList list) {
		Iterator<String> ite = list.iterator();
		Stack<Integer> stack = new Stack<Integer>();
		String temp;
		int second, first;
		while (ite.hasNext()) {
			temp = ite.next();
			if (temp.equals("+")) {
				second = stack.pop();
				first = stack.pop();
				stack.push(first + second);
			} else if (temp.equals("-")) {
				second = stack.pop();
				first = stack.pop();
				stack.push(first - second);
			} else if (temp.equals("*")) {
				second = stack.pop();
				first = stack.pop();
				stack.push(first * second);
			} else if (temp.equals("/")) {
				second = stack.pop();
				first = stack.pop();
				stack.push(first / second);
			} else {
				stack.push(Integer.parseInt(temp));
			}
		}

		return stack.pop();
	}

	public static void main(String[] args) {
		Solution s = new Solution();
		System.out.println(s.calculate("1-2+3"));
		System.out.println(s.calculate("1-(2+3)"));
		System.out.println(s.calculate("2*4-2*3"));
	}
}