193、【栈与队列】leetcode ——面试题 16.26. 计算器(C++版本)
2023-09-11 14:20:01 时间
题目描述
Problem: 面试题 16.26. 计算器
思路
采取双栈的形式,分为操作数栈和运算符栈。
解题方法
对于操作数,遍历到一个数就压入,需要进行操作时,再弹出。对于运算符,当栈中元素为空或者遍历元素比栈中元素优先级小的话,只压入栈。若遍历元素比栈中元素优先级大的化,则先对栈中元素进行运算操作,然后再压入栈。最后结尾,若运算符栈非空或者操作数栈中个数不为1,则是因为最后一个压入元素没有进行运算,对剩余元素进行操作。
复杂度
- 时间复杂度:
添加时间复杂度, 示例: O ( n ) O(n) O(n)
- 空间复杂度:
添加空间复杂度, 示例: O ( n ) O(n) O(n)
Code
class Solution {
public:
int calculate(string s) {
stack<int> operands;
stack<int> operators;
int i = 0;
while (i < s.size()) {
// 处理空格
if(s[i] == ' ') {
while(s[i] == ' ') {
i++;
}
// 取数字
} else if(isdigit(s[i])) {
int num = 0;
// 从个位到高位依次取数构造
for(; i < s.size() && isdigit(s[i]); i++) {
num = num * 10 + (s[i] - '0');
}
operands.push(num);
// 取运算符
} else {
// 运算符栈中不为空时,让栈顶元素和s[i]进行比较,如果s[i]的优先级低,则让栈顶元素先操作。
while(!operators.empty() && !priority(s[i], operators.top())){
calc(operands, operators);
}
operators.push(s[i]);
i++;
}
}
while(!operators.empty()) {
calc(operands, operators);
}
return operands.top();
}
void calc(stack<int>& operands, stack<int>& operators) {
int b = operands.top(); operands.pop();
int a = operands.top(); operands.pop();
int op = operators.top(); operators.pop();
int res = 0;
switch(op) {
case '+' : res = a + b; break;
case '-' : res = a - b; break;
case '*' : res = a * b; break;
case '/' : res = a / b; break;
default : ;
}
operands.push(res);
return ;
}
// a的优先级是否高于b
bool priority(int a, int b) {
// a为加减一类,则已经为最低一类级别优先级,返回false
if(a == '+' || a == '-') {
return false;
// a为乘除一类,则优先级更高
} else if (a == '*' || a == '/') {
// 当b比a优先级低时,返回true。同级,则返回false
return (b == '+' || b == '-');
}
return false;
}
};
相关文章
- C/C++面试题总结(1)
- 一次失败的面试经历:我只想找个工作,你却用面试题羞辱我
- c++程序猿经典面试题(2)
- java面试题总结
- Zookeeper面试题
- 面试题:单线程redis还这么快
- 【吐血整理】CSDN上各个大厂网络安全岗面试题及个人模拟面试经验精选总结
- JAVA面试题Forward和Redirect区别
- 理清gcc、libc、libstdc++的关系(libstdc++是gcc搞的,libc++是llvm搞的,他们都是C++标准库的实现)
- 经典的面试题,(这是著名的约瑟夫环问题)
- 2022MyBatis面试常问面试题
- 这几道const和iota的面试题你能做对吗?
- 201、【数组】leetcode ——面试题 17.05. 字母与数字(C++版本)