## Basic Calculator II

07/16/2016 String

## Question

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.

You may assume that the given expression is always valid.

Some examples:

"3+2*2" = 7
" 3/2 " = 1
" 3+5 / 2 " = 5


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

## Solution

Result: Accepted Time: 8 ms

Here should be some explanations.


#include <stdio.h>
#include <ctype.h>

int getlv(char ch)
{
switch(ch)
{
case '+':
case '-':
return 1;
case '*':
case '/':
return 2;
default:
return 0;
}
}

int  operate(int a ,int b,char tmp)
{
///printf(" %d %c % d\n",a,tmp,b);
switch (tmp)
{
case '+':
return a + b;
case '-':
return a - b;
case '*':
return a * b;
case '/':
return a/b;
}
}

int deal(const char data[])
{
char sta[100],tmp;
int top=0,ptr=0;
int ans[100],atop=0;
int value=0;
while(data[ptr]!='\0')
{
if(isdigit(data[ptr]))
{
value = 0;
while(data[ptr]>='0'&&data[ptr]<='9')
value = value * 10 + data[ptr++] - '0';
ans[atop++] = value;

}
tmp=data[ptr++];
if(tmp=='\0') break;
if(top == 0)
sta[top++] = tmp;
else if((tmp=='-'||tmp=='+'||tmp=='*'||tmp=='/'))
{
int curlv=getlv(tmp);
int stalv=getlv(sta[top-1]);
while(curlv<=stalv)
{
ans[atop - 2] = operate(ans[atop -2],ans[atop - 1],sta[--top]);
atop --;
if(atop>0)
stalv=getlv(sta[top-1]);
else
break;
}
sta[top++] = tmp;
}
}
while(top > 0)
{
ans[atop - 2] = operate(ans[atop -2],ans[atop - 1],sta[--top]);
atop --;
}
///printf("%d\n",ans[0]);
return ans[0];
}

int calculate(char* data)
{
return deal(data);
}


Complexity Analytics

• Time Complexity: $O(n)$
• Space Complexity: $O(n)$