博客

class Solution {
public:
	int fun(int index, vector<long int> &v) //index对应数字(一个数字一个运算符)
	{
		
		if (index + 1 == v.size()) //如果是最后一个
		{
			return v[index];
		}
		else //乘除直接算 加减算后面的 先乘除后加减
		{
			
			int temp = v[index];
			
			while (v[index+1]==-3||v[index+1]==-4)//乘除一口气算完 -3,-4,*,/
			{
				if (v[index + 1] == -3) 
				{
					
					temp = temp * v[index + 2];
				}
				else if(v[index + 1] == -4)
				{
					
					temp = temp / v[index + 2];
				}
				index += 2;//跳过一个运算符  直接到数字（数字以及计算过了）
				
				if (index == v.size() - 1) //到头了
				{
					return temp;
				}
			}
			
			if (v[index + 1] == -1) //+
			{
				return temp + fun(index+2, v);
			}
			
			if (v[index + 1] == -2)//-下一个数字乘-1
			{
                v[index+2]*=-1;
				return temp + fun(index + 2, v);
			}
			return temp;
		}
	}
	int calculate(string s) 
	{
		int ans;
		vector<long int> v;//注意整形不够存的
		
		if (s.empty())return 0;
		for (int i = 0; i < s.size(); i++) 
		{
			long int temp = 0;
			if (s[i] == ' ')continue;//空格直接跳过
			else if (s[i] == '+') temp = -1;
			else if (s[i] == '-') temp = -2;
			else if (s[i] == '*') temp = -3;
			else if (s[i] == '/') temp = -4;
			else if(s[i]>='0'&&s[i]<='9')
			{
				temp = s[i] - '0';
				while (i+1<s.size()&&s[i+1]==' '|| (s[i+1] >= '0'&&s[i+1] <= '9'))//下一个点不能是空格或者数字而且不能越界 如果是要改变
				{
					if (s[i + 1] == ' ') 
					{
						i++;
					}
					else if (s[i + 1] >= '0'&&s[i + 1] <= '9') 
					{
						temp = temp * 10 + s[i + 1] - '0';
						i++;
					}
					
				}
			}
			v.emplace_back(temp);
		}
		//+-*/ 分别用-1，-2，-3，-4代替
		ans = fun(0, v);//肯定是一个数字接着一个运算符
		return ans;
	}
};

解法：空间复杂度比较高，把数字和字符全部转换成数字存在vector，乘除直接算，加减法全部转换成加法，减法转换成加法的方法是把减号后面一个数字乘以-1。

227. Basic Calculator II

Medium

656102FavoriteShare

Implement 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.

Example 1:

Input: "3+2*2"
Output: 7

Example 2:

Input: " 3/2 "
Output: 1

Example 3:

Input: " 3+5 / 2 "
Output: 5