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```

2.思路：

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

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

3.代码

```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;
}

}```

```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]==')')
{
}
int temp = calculateHelper(s, location);
next = location ;
location = next + 1;
total = (isPlus)?(total - temp) : (total + temp);

}
}
public:
int calculate(string s) {
int location = 0;//指示位置的指针
return calculate(s, location);
}
};```

4.另一种思路：

```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();
}
};```

0 条评论

相关文章

15020

19440

13150

43230

17230

50620

26340

11210

26530

SQL中GROUP BY用法示例

GROUP BY我们可以先从字面上来理解，GROUP表示分组，BY后面写字段名，就表示根据哪个字段进行分组，如果有用Excel比较多的话，GROUP BY比较类...

5.1K20