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,+,-,(,)和空白符号。
可以认为所有的计算数均为非负值。可以认为题目的输入均为有效算式。字符串中可能有空格,你需要自己处理掉。
递归地计算每个子式相加减的值。
何为子式?认为整个算式是第一个子式。第一个被括号括起来的式子是第二个子式。依次类推。
例如,
(1+(4+5+2)-3)+(6+8)
中,第一个子式是(1+(4+5+2)-3)+(6+8)。第二个子式是(1+(4+5+2)-3)。第三个是(4+5+2)。第四个是(6+8)。
那么,
给出一份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); } };
使用栈来完成运算,是常见的算式解法。这里给出一份用两个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(); } };