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.

Some examples:

"1 + 1" = 2

" 2-1 + 2 " = 3

"(1+(4+5+2)-3)+(6+8)" = 23

Note: Do not use the eval built-in library function.

Java:

public int calculate(String s) {

	// delte white spaces

	s = s.replaceAll(" ", "");

	Stack<String> stack = new Stack<String>();

	char[] arr = s.toCharArray();

	StringBuilder sb = new StringBuilder();

	for (int i = 0; i < arr.length; i++) {

		if (arr[i] == ' ')

			continue;

		if (arr[i] >= '0' && arr[i] <= '9') {

			sb.append(arr[i]);

			if (i == arr.length - 1) {

				stack.push(sb.toString());

			}

		} else {

			if (sb.length() > 0) {

				stack.push(sb.toString());

				sb = new StringBuilder();

			}

			if (arr[i] != ')') {

				stack.push(new String(new char[] { arr[i] }));

			} else {

				// when meet ')', pop and calculate

				ArrayList<String> t = new ArrayList<String>();

				while (!stack.isEmpty()) {

					String top = stack.pop();

					if (top.equals("(")) {

						break;

					} else {

						t.add(0, top);

					}

				}

				int temp = 0;

				if (t.size() == 1) {

					temp = Integer.valueOf(t.get(0));

				} else {

					for (int j = t.size() - 1; j > 0; j = j - 2) {

						if (t.get(j - 1).equals("-")) {

							temp += 0 - Integer.valueOf(t.get(j));

						} else {

							temp += Integer.valueOf(t.get(j));

						}

					}

					temp += Integer.valueOf(t.get(0));

				}

				stack.push(String.valueOf(temp));

			}

		}

	}

	ArrayList<String> t = new ArrayList<String>();

	while (!stack.isEmpty()) {

		String elem = stack.pop();

		t.add(0, elem);

	}

	int temp = 0;

	for (int i = t.size() - 1; i > 0; i = i - 2) {

		if (t.get(i - 1).equals("-")) {

			temp += 0 - Integer.valueOf(t.get(i));

		} else {

			temp += Integer.valueOf(t.get(i));

		}

	}

	temp += Integer.valueOf(t.get(0));

	return temp;

}

Python:

class Solution:

    # @param {string} s

    # @return {integer}

    def calculate(self, s):

        operands, operators = [], []

        operand = ""

        for i in reversed(xrange(len(s))):

            if s[i].isdigit():

                operand += s[i]

                if i == 0  or not s[i-1].isdigit():

                    operands.append(int(operand[::-1]))

                    operand = ""

            elif s[i] == ')' or s[i] == '+' or s[i] == '-':

                operators.append(s[i])

            elif s[i] == '(':

                while operators[-1] != ')':

                    self.compute(operands, operators)

                operators.pop()

        while operators:

            self.compute(operands, operators)

        return operands[-1]

    def compute(self, operands, operators):

        left, right = operands.pop(), operands.pop()

        op = operators.pop()

        if op == '+':

            operands.append(left + right)

        elif op == '-':

            operands.append(left - right)

C++:

class Solution {

public:

    int calculate(string s) {

        int res = 0, sign = 1, n = s.size();

        stack<int> st;

        for (int i = 0; i < n; ++i) {

            char c = s[i];

            if (c >= '0') {

                int num = 0;

                while (i < n && s[i] >= '0') {

                    num = 10 * num + s[i++] - '0';

                }

                res += sign * num;

                --i;

            } else if (c == '+') {

                sign = 1;

            } else if (c == '-') {

                sign = -1;

            } else if (c == '(') {

                st.push(res);

                st.push(sign);

                res = 0;

                sign = 1;

            } else if (c == ')') {

                res *= st.top(); st.pop();

                res += st.top(); st.pop();

            }

        }

        return res;

    }

};

C++:

class Solution2 {

public:

    int calculate(string s) {

        stack<int> operands;

        stack<char> operators;

        string operand;

        for (int i = s.length() - 1; i >= 0; --i) {

            if (isdigit(s[i])) {

                operand.push_back(s[i]);

                if (i == 0 || !isdigit(s[i - 1])) {

                    reverse(operand.begin(), operand.end());

                    operands.emplace(stoi(operand));

                    operand.clear();

                }

            } else if (s[i] == ')' || s[i] == '+' || s[i] == '-') {

                operators.emplace(s[i]);

            } else if (s[i] == '(') {

                while (operators.top() != ')') {

                    compute(operands, operators);

                }

                operators.pop();

            }

        }

        while (!operators.empty()) {

            compute(operands, operators);

        }

        return operands.top();

    }

    void compute(stack<int>& operands, stack<char>& operators) {

        const int left = operands.top();

        operands.pop();

        const int right = operands.top();

        operands.pop();

        const char op = operators.top();

        operators.pop();

        if (op == '+') {

            operands.emplace(left + right);

        } else if (op == '-') {

            operands.emplace(left - right);

        }

    }

};

类似题目：

[LeetCode] 227. Basic Calculator II 基本计算器 II

All LeetCode Questions List 题目汇总

巴特西

[LeetCode] 224. Basic Calculator 基本计算器

All LeetCode Questions List 题目汇总

最新文章

热门文章