BM49. 表达式求值
描述
请写一个整数计算器，支持加减乘三种运算和括号。
数据范围：
，保证计算结果始终在整型范围内
要求：空间复杂度： )
，时间复杂度
示例1
输入:
"1+2"
输出:
3
示例2
输入:
"(2*(3-4))*5"
输出:
-10
示例3
输入:
"3+2*3*4-1"
输出:
26
BM49. 表达式求值
描述
示例1
输入:
"1+2"
输出:
3
示例2
输入:
"(2*(3-4))*5"
输出:
-10
示例3
输入:
"3+2*3*4-1"
输出:
26
C++ 解法, 执行用时: 2ms, 内存消耗: 292KB, 提交时间: 2021-09-18
class Solution {
public:
int solve(string s) {
stack<int> val;
stack<char> ops;
for(int i=0; i<=s.length();){
if(s[i]>='0'&&s[i]<='9')
val.push(toInt(s, i));
else if(ops.empty()||ops.top()=='('||s[i]=='(')
ops.push(s[i++]);
else if(s[i]=='*'){
int t1=val.top(),t2=toInt(s, ++i);
val.pop();
val.push(t1*t2);
}
else{
int t2=val.top();
val.pop();
int t1=val.top();
val.pop();
if(ops.top()=='+')
val.push(t1+t2);
else if(ops.top()=='-')
val.push(t1-t2);
else if(ops.top()=='*')
val.push(t1*t2);
ops.pop();
if(s[i]==')'){
ops.pop();
i++;
}
else if(i==s.length())
break;
}
}
return val.top();
}
int toInt(string s,int &i){
int tmp=0;
while(s[i]<='9'&&s[i]>='0')
tmp=tmp*10+s[i++]-'0';
return tmp;
}
};
C++ 解法, 执行用时: 2ms, 内存消耗: 320KB, 提交时间: 2021-09-15
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
* 返回表达式的值
* @param s string字符串 待计算的表达式
* @return int整型
*/
int solve(string s) {
// write code here
int n = s.length();
int pos = 0;
stack<int> num;
stack<char> op;
while(pos < n){
char c = s[pos];
if(c == '+' || c =='-'){
while(!op.empty()){
if(op.top() == '('){
break;
}else{
if(op.top() == '+'){
op.pop();
int n1 = num.top();
num.pop();
int n2 = num.top();
num.pop();
num.push(n1+n2);
}else if(op.top() == '-'){
op.pop();
int n1 = num.top();
num.pop();
int n2 = num.top();
num.pop();
num.push(n2-n1);
}else if(op.top() == '*'){
op.pop();
int n1 = num.top();
num.pop();
int n2 = num.top();
num.pop();
num.push(n1*n2);
}
}
}
op.push(c);
pos++;
continue;
}
if(c >= '0' && c <= '9'){
int start = pos;
int end = pos;
while(end < n && s[end] >= '0' && s[end] <= '9'){
end++;
}
int curN = stoi(s.substr(start,end-start));
num.push(curN);
pos = end;
continue;
}
if(c == '('){
op.push(c);
pos++;
continue;
}
if(c == ')'){
while(op.top() != '('){
char ope = op.top();
op.pop();
if(ope == '*'){
int n1 = num.top();
num.pop();
int n2 = num.top();
num.pop();
num.push(n1*n2);
}else if(ope == '/'){
int n1 = num.top();
num.pop();
int n2 = num.top();
num.pop();
num.push(n2/n1);
}else if(ope == '+'){
int n1 = num.top();
num.pop();
int n2 = num.top();
num.pop();
num.push(n1+n2);
}else{
int n1 = num.top();
num.pop();
int n2 = num.top();
num.pop();
num.push(n2-n1);
}
}
op.pop();
pos++;
continue;
}
if(c == '*' || c == '/'){
while(!op.empty()){
if(op.top() == '(' || op.top() == '+' || op.top() == '-'){
break;
}else{
int n1 = num.top();
num.pop();
int n2 = num.top();
num.pop();
if(op.top() == '*'){
num.push(n1*n2);
}else if(op.top() == '/'){
num.push(n2/n1);
}
op.pop();
}
}
op.push(c);
pos++;
continue;
}
}
while(!op.empty()){
char ope = op.top();
op.pop();
int n1 = num.top();
num.pop();
int n2= num.top();
num.pop();
if(ope == '+'){
num.push(n1+n2);
}else if(ope == '-'){
num.push(n2-n1);
}else{
num.push(n1*n2);
}
}
return num.top();
}
};
C++ 解法, 执行用时: 2ms, 内存消耗: 320KB, 提交时间: 2020-12-06
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
* 返回表达式的值
* @param s string字符串 待计算的表达式
* @return int整型
*/
int solve(string s) {
// write code here
stack<int> stk;
int n = s.size();
int num = 0, result = 0;
char flag = '+';
for(int i = 0; i < n; i++){
char c = s[i];
if(c <= '9' && c >= '0') num = num * 10 + c -'0';
if(c == '('){
int j = i + 1;
int count = 1;
while(count){
if(s[j] == ')') count--;
else if(s[j] == '(') count++;
j++;
}
num = solve(s.substr(i + 1, j - i - 1));
i = j - 1;
}
if(c == '(' || c == ')' || c == '+' || c == '-' || c == '*' || i == n - 1){
if(flag == '+') stk.push(num);
if(flag == '-') stk.push(-num);
if(flag == '*'){
num *= stk.top();
stk.pop();
stk.push(num);
}
flag = c;
num = 0;
}
}
while(!stk.empty()){
result += stk.top();
stk.pop();
}
return result;
}
};
C++ 解法, 执行用时: 2ms, 内存消耗: 328KB, 提交时间: 2021-09-09
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
* 返回表达式的值
* @param s string字符串 待计算的表达式
* @return int整型
*/
int solve(string s) {
// write code here
int ans = 0; //用于返回当前字符串的计算结果
stack<int> sum; //用于求和
char sign = '+'; //记录前一个符号，初始化为+，因为可以看成当前字符串前先加0
int num = 0; //用于将连续数字字符串转化成数字或者记录递归结果
for(int i = 0; i < s.size(); i++) { //遍历每一个字符
if(s[i] >= '0' && s[i] <= '9') //先处理数字字符
num = 10 * num + s[i] - '0'; //进位后加个位数
if(s[i] == '(') { //对于括号
int left = i++, count = 1; //用left记录最左括号位置，count记录左括号数，i当成右指针右移一格
while(count > 0) { //最终目的是找到与最左括号匹配的右括号，类似于栈操作
if(s[i] == '(') count++;
else if(s[i] == ')') count--;
i++;
}
num = solve(s.substr(left + 1, i - left - 2)); //迭代计算括号内数值，注意不要包含最左最右括号，不然会死循环
i--; //此时i是最右括号下一位，需要左移一位防止最右括号在字符串尾时发生越界从而使下面的判定失效
}
if(i == s.size() - 1 || s[i] == '+' || s[i] == '-' || s[i] == '*') { //对于字符串尾，或者加减乘，此时我们用的符号是上一次的，结算当前数字
if(sign == '+') sum.push(num); //加法入栈
else if(sign == '-') sum.push(-num); //减法相当于加负数
else if(sign == '*') sum.top() *= num; //乘法与栈顶相乘
sign = s[i]; //更新符号，若为末尾的右括号也无妨，因为马上就退出循环了
num = 0; //重置当前数
}
}
while(!sum.empty()) { //将栈内所有数字相加
ans += sum.top();
sum.pop();
}
return ans; //返回当前字符串计算结果
}
};
C++ 解法, 执行用时: 2ms, 内存消耗: 332KB, 提交时间: 2021-06-06
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
* 返回表达式的值
* @param s string字符串 待计算的表达式
* @return int整型
*/
int solve(string s) {
int res = 0;
stack<int> sumStack;
char sign = '+';
int num = 0;
for(int i=0; i<s.length(); ++i)
{
if(s[i] >= '0' && s[i]<='9')
{
num = num * 10 + s[i]-'0';
}
if(s[i] == '(')
{
int left = i++, count = 1;
while(count>0)
{
if(s[i] == '(')
count++;
else if(s[i] == ')')
count--;
++i;
}
num = solve(s.substr(left+1, i-left-2));
--i;
}
if(i==s.length()-1 || s[i]=='+' || s[i]=='-' || s[i]=='*')
{
if(sign == '+')
sumStack.push(num);
else if(sign == '-')
sumStack.push(-num);
else if(sign =='*')
sumStack.top()*=num;
sign = s[i];
num = 0;
}
}
while(!sumStack.empty())
{
res+=sumStack.top();
sumStack.pop();
}
return res;
}
};