LeetCode Q227 Basic Calculator II

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:

The key is to "look back" when encounter a new operator. We compute results of "*" and "/" as we goes, and save all signed numbers and results in a stack. What left at the end is to only compute the sum of all elements in the stack.

	class Solution {
	public:
	void ProcessPast(stack<int>& nums, int& presign, int& num){
	if(presign=='-'||presign=='+'){
	num=presign=='-'? -1*num:num;
	nums.push(num);
	}
	if(presign=='*'||presign=='/'){
	int prenum=nums.top();
	nums.pop();
	int rst=presign=='*'?prenum*num:prenum/num;
	nums.push(rst);
	}
	}
	int calculate(string s) {
	stack<int> nums;
	int presign='+';
	int num=0;
	for(char c: s){
	if(isdigit(c)){
	num=num*10+c-'0';
	}else{
	if(c==' ') continue;
	ProcessPast(nums, presign, num);
	presign=c;
	num=0;
	}
	}
	ProcessPast(nums, presign, num);
	int sum=0;
	while(!nums.empty()){
	sum=sum+nums.top();
	nums.pop();
	}
	return sum;
	}
	};

view raw Q227BasicCalculatorII.cpp hosted with ❤ by GitHub

Round 2 solution:

	class Solution {
	public:
	int calculate(string s) {
	stack<int> nums, ops;
	int sign=1;
	int num = 0 ;
	for(int i = 0; i<s.length(); i++){
	char c= s[i];
	if(isdigit(c)&&i!=s.length()-1){
	num = num*10+c-'0';
	}else{
	if(c==' ') continue;
	num = isdigit(c)? num*10+c-'0':num;
	num = num*sign;
	nums.push(num);
	num = 0;
	if(!ops.empty()&&(ops.top()=='*'||ops.top()=='/')){
	int tmp1 = nums.top(); nums.pop();
	int tmp2 = nums.top(); nums.pop();
	int tmp3 = ops.top()=='*'? tmp1*tmp2:tmp2/tmp1;
	ops.pop();
	nums.push(tmp3);
	}
	if(c=='+') sign=1;
	if(c=='-') sign=-1;
	if(c=='*'||c=='/') ops.push(c);
	}
	}
	int rst=0;
	while(!nums.empty()){
	rst+=nums.top();
	nums.pop();
	}
	return num==0? rst:num;
	}
	};

view raw Q227.cpp hosted with ❤ by GitHub