题解 | #表达式求值#

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 返回表达式的值
     * @param s string字符串 待计算的表达式
     * @return int整型
     */
    static LinkedList<Integer> num = new LinkedList<Integer>();
	static LinkedList<Character> ope = new LinkedList<Character>();

	static boolean isnum(char s)
	{
		return s >= '0' && s <= '9';
	}

	static void solve()
	{
		int b = num.poll();
		int a = num.poll();

		char s = ope.poll();

		int x = 0;
		if (s == '+')
			x = a + b;
		else if (s == '-')
			x = a - b;
		else if (s == '*')
			x = a * b;

		num.push(x);
	}

	static int shun(char s)
	{
		if (s == '+' || s == '-')
			return 1;
		return 2;
	}

	public int solve(String str)
	{
		int len = str.length();
		char s[] = str.toCharArray();

		for (int i = 0; i < len; i++)
		{
			if (isnum(s[i]))
			{
				int j = i;
				int x = 0;
				while (j < len && isnum(s[j]))
					x = x * 10 + s[j++] - '0';
				i = j - 1;
				num.push(x);
			} else if (s[i] == '(')
				ope.push(s[i]);
			else if (s[i] == ')')
			{
				while (ope.peek() != '(')
					solve();
				ope.poll();
			} else
			{
				while (ope.size() != 0 && ope.peek() != '(' && shun(ope.peek()) >= shun(s[i]))
					solve();
				ope.push(s[i]);
			}
		}

		while (ope.size() != 0)
			solve();

		return num.poll();
	}
}