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:
" 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)。第三个是(4+5+2)。第四个是(6+8)。
那么，
要求第一个子式的值，就等于求第二个子式+第四个子式。
要求第二个子式的值，就等于求1+第三个子式-3。
- 所以，首先要有一个函数1，它接受一个指针指向某个子式的开头，返回这个子式的值。
- 其次，要有一个函数2，用于把字符串中的1啊，23啊，84啊之类的字符串转换成相应的数值1，23，84。如果要被转换的字符是'('，说明要转换的内容是一个子式，那么就用函数1处理。
3.代码
给出一份JAVA实现：
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++实现：
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用于保存操作数，另一个用于保存操作符。思路就是压入操作数，遇到操作符后把操作数取出来，与字符串中下一个操作数相运算，再压入栈，同时把该操作符出栈丢弃。
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();
}
};
本文链接：Basic Calculator 基本计算器-Leetcode，转载请注明。