224. 基本计算器
1.题目描述及示例
题目描述 实现一个基本的计算器来计算一个简单的字符串表达式的值。 字符串表达式可以包含左括号 ( ，右括号 )，加号 + ，减号 -，非负整数和空格 。
示例
2.题解思路及代码
思路 参考《算法笔记》中，关于栈这节的内容代码
public int calculate(String s) {
s=s.trim();
int [] nums=new int[s.length()];
int [] ops=new int[s.length()];
int numsIndex=-1,opsIndex=-1;
for(int i=0;i<s.length();i++)
{
char c=s.charAt(i);
if (c>='0'&&c<='9')
{
int temp=0;
int j=i;
while (c>='0'&&c<='9')
{
temp=temp*10+c-'0';
j++;
if (j==s.length())
break;
c=s.charAt(j);
}
numsIndex++;
nums[numsIndex]=temp;
i=j-1;
}
else if (c=='-'||c=='+')
{
while (opsIndex!=-1&&ops[opsIndex]!=-1)
{
numsIndex++;
nums[numsIndex]=ops[opsIndex];
opsIndex--;
}
if (opsIndex==-1||ops[opsIndex]==-1)
{
opsIndex++;
if (c=='-')
ops[opsIndex]=-3;
else
ops[opsIndex]=-2;
}
}
else if (c=='(')
{
opsIndex++;
ops[opsIndex]=-1;
}
else if (c==')')
{
while (ops[opsIndex]!=-1)
{
numsIndex++;
nums[numsIndex]=ops[opsIndex];
opsIndex--;
}
opsIndex--;
}
}
while (opsIndex!=-1)
{
numsIndex++;
nums[numsIndex]=ops[opsIndex];
opsIndex--;
}
Stack<Integer>stack=new Stack<Integer>();
for (int i=0;i<=numsIndex;i++)
{
if (nums[i]!=-3&&nums[i]!=-2)
{
stack.push(nums[i]);
}
else
{
int b=stack.pop();
int a=stack.pop();
if (nums[i]==-2)
stack.push(a+b);
else
stack.push(a-b);
}
}
return stack.pop();
}
