转载

Basic Calculator 基本计算器-Leetcode

1.题目:

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

题目要求是,实现一个基本的计算器,它接受一个字符串作为输入,实现加法减法和小括号。字符串中有0-9,+,-,(,)和空白符号。

可以认为所有的计算数均为非负值。可以认为题目的输入均为有效算式。字符串中可能有空格,你需要自己处理掉。

2.思路:

递归地计算每个子式相加减的值。

何为子式?认为整个算式是第一个子式。第一个被括号括起来的式子是第二个子式。依次类推。

例如,

(1+(4+5+2)-3)+(6+8)

中,第一个子式是(1+(4+5+2)-3)+(6+8)。第二个子式是(1+(4+5+2)-3)。第三个是(4+5+2)。第四个是(6+8)。

那么,

要求第一个子式的值,就等于求第二个子式+第四个子式。

要求第二个子式的值,就等于求1+第三个子式-3。

  • 所以,首先要有一个函数1,它接受一个指针指向某个子式的开头,返回这个子式的值。
  • 其次,要有一个函数2,用于把字符串中的1啊,23啊,84啊之类的字符串转换成相应的数值1,23,84。如果要被转换的字符是'(',说明要转换的内容是一个子式,那么就用函数1处理。

3.代码

给出一份JAVA实现:

public class Solution{  public int calculate(String s){//这个就是函数1   int ans=0;   int sign=1;   while (location<s.length()){    ans+=(helper(s)*sign);    if (location>=s.length()) break;    if (s.charAt(location)==')') {     location++;     return ans;    }    sign=(s.charAt(location)=='-')?-1:1;    location+=1;   }   return ans;  }  private int location=0;//这个就是给出子式位置的指针  private int helper(String s){//这个就是函数2   int op=0;   while (location<s.length()&&(Character.isDigit(s.charAt(location))||Character.isSpaceChar(s.charAt(location)))){    if (Character.isDigit(s.charAt(location))){     op*=10;     op+=(s.charAt(location)-'0');    }    location++;   }   if (location<s.length()&&s.charAt(location) == '('){    location++;    return calculate(s);   }   return op;  } } 

同时,给出一份C++实现:

class Solution { private:  int calculateHelper(string& s, int& location){//函数2   while (s[location]==' ')   {    location++;   }   if (s[location]=='(')   {    return calculate(s, ++location);   }   int ans=0;   while (s[location]>='0'&& s[location]<='9')   {    while (s[location] == ' ')    {     location++;    }    ans *= 10;    ans += (s[location] - '0');    location++;   }   return ans;  }  int calculate(string& s, int& location){//函数1   int total = 0;   int next = 0;   for (next = location;next<s.length();)   {    bool isPlus = (s[next] == '-');//检查是做加法还是减法    if (s[next]==')')    {     return total;    }    int temp = calculateHelper(s, location);    next = location ;    location = next + 1;    total = (isPlus)?(total - temp) : (total + temp);   }   return total;  } public:  int calculate(string s) {   int location = 0;//指示位置的指针   return calculate(s, location);  } }; 

4.另一种思路:

使用栈来完成运算,是常见的算式解法。这里给出一份用两个stack来解题的算法,一个stack用于保存操作数,另一个用于保存操作符。思路就是压入操作数,遇到操作符后把操作数取出来,与字符串中下一个操作数相运算,再压入栈,同时把该操作符出栈丢弃。

class Solution { private:  int toInt(string& s, int& location){   int ans = 0;   while (location<s.length() && s[location] >= '0'&&s[location] <= '9'){    ans *= 10;    ans += (s[location] - '0');    location++;   }   return ans;  }  void calculateTwo(stack<char> &op, stack<int> &st)  {   char c = op.top();   op.pop();   int n1 = st.top();   st.pop();   int n2 = st.top();   st.pop();   if (!op.empty() && op.top() == '-')   {    op.pop();    op.push('+');    n2 = -n2;   }   n2 = (c == '+') ? (n2 + n1) : (n2 - n1);   st.push(n2);  } public:  int calculate(string s) {   stack<int> st;   stack<char> op;   bool isNeg = false;   for (int i = 0; i<s.length();){    if (s[i] == ' ') {     i++;     continue;    }    if (s[i] >= '0'&&s[i] <= '9'){     int j = toInt(s, i);     st.push(j);     while (!op.empty()){      char c = op.top();      if (c == '('){       break;      }      calculateTwo(op, st);     }    }    else if (s[i] == ')'){     while (!op.empty()){      char c = op.top();      if (c=='(')      {       op.pop();       break;      }      calculateTwo(op, st);     }     i++;    }    else{     op.push(s[i]);     i++;    }   }   while (!op.empty())   {    calculateTwo(op, st);   }   return st.top();  } }; 
正文到此结束
Loading...