224、Basic Calculator

Implement a basic calculator to evaluate a simple expression string.

The expression string may contain open ( and closing parentheses ), the plus + or minus sign -, non-negative integers and empty spaces .

You may assume that the given expression is always valid.

Some examples:

"1 + 1" = 2

" 2-1 + 2 " = 3

"(1+(4+5+2)-3)+(6+8)" = 23

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

这个题目的思路要考虑的情况比较多，主要的想法是：符号相当于数字之前的正负号；默认在第一个数字之前加了正号。
有一个基准result为0，可能有5种情况：
/*
1、如果是数字，就转换为十进制；考虑123+122等(isdigit函数)；
2、如果是+号，用result去和上一个符号(sign)和数字(number)运算，然后将number清空，符号'+'保存；
3、'-'同上；
4、如果是'('那么利用一个栈，将之前的结果result保存，将'('前的符号sign保存；然后将result和sign初始化(类似于重新开始计算)；
5、如果是')'那么这个括号中的result要和之前保存的result(stack)还有sign(stack)进行计算。
*/

 1  int calculate(string s) {

 2         long int result=0;

 3         stack<long int> s1;

 4         int sign=1,i=0;

 5         int number=0;

 6       //  2+1+(4+5+2)-3+7

 7         while(i<s.size())

 8         {

 9             //123

10             if(isdigit(s[i]))

11             {

12                 number=number*10+(s[i]-'0');

13             }

14             else if(s[i]=='+')

15             {

16                 result+=sign*number;

17                 sign=1;

18                 number=0;

19             }

20             else if(s[i]=='-')

21             {

22                 result+=sign*number;

23                 sign=-1;

24                 number=0;

25             }

26             else if(s[i]=='(')

27             {

28                 s1.push(result);

29                 s1.push(sign);

30                 result=0;

31                 sign=1;

32             }

33             //符号是括号中result前的正负号。

34             else if(s[i]==')')

35             {

36                 result+=sign*number;

37                 //非常重要

38                 number=0;//否则括号前一个数字要被计算两次。

39                 long temp=s1.top();

40                 s1.pop();

41                 result*=temp;

42                 result+=s1.top();

43                 s1.pop();

44             }

45             i++;

46         }

47         result+=sign*number;//每次遇到下一个符号即数字后一个符号，才去算上一个数字及其前面的正负号。

48         return result;

49     }

50 };

巴特西

224、Basic Calculator

最新文章

热门文章