题目
文本
给你一个字符串表达式 s ,请你实现一个基本计算器来计算并返回它的值。
整数除法仅保留整数部分。
示例 1:
输入:s = "3+2*2"
输出:7
示例 2:
输入:s = " 3/2 "
输出:1
示例 3:
输入:s = " 3+5 / 2 "
输出:5
提示:
1 <= s.length <= 3 * 105
s 由整数和算符 ('+', '-', '*', '/') 组成,中间由一些空格隔开
s 表示一个 有效表达式
表达式中的所有整数都是非负整数,且在范围 [0, 231 - 1] 内
题目数据保证答案是一个 32-bit 整数
来源:力扣(LeetCode)
模板
int calculate(char * s){
}
解答
分析
本题依旧是计算器运算的实现。对于题目的要求我们依旧是从两个方面入手解决,输入的是字符串s。s中所包含的有两种元素(不包括空格),就是数字和运算符两种。运算数字num的处理就是通过简单的差值转化。
if (isdigit(s[i])) {
num = num * 10 + (int)(s[i] - '0');
}
对于运算符我们需要考虑"+-* / "的四种符号处理方法,很显然我们要做的是对于 "* /" 两种进行优先处理。所以这里需要用到栈。
+-符号后面的num可以直接感觉符号决定压入num还是-num
case '+':
stk[top++] = num;
break;
case '-':
stk[top++] = -num;
break;
而对于*和/两种情况,需要在入栈时就对元素进行操作,来达到有限操作乘除的效果。达到这效果就是对于栈顶元素进行处理,这样最后的统计时就是已经操作过乘除的元素求和就行了。
case '*':
stk[top - 1] *= num;
break;
default:
stk[top - 1] /= num;
}
完整源码
int calculate(char* s) {
int n = strlen(s);
int stk[n], top = 0;
char preSign = '+';
int num = 0;
for (int i = 0; i < n; ++i) {
if (isdigit(s[i])) {
num = num * 10 + (int)(s[i] - '0');
}
if (!isdigit(s[i]) && s[i] != ' ' || i == n - 1) {
switch (preSign) {
case '+':
stk[top++] = num;
break;
case '-':
stk[top++] = -num;
break;
case '*':
stk[top - 1] *= num;
break;
default:
stk[top - 1] /= num;
}
preSign = s[i];
num = 0;
}
}
int ret = 0;
for (int i = 0; i < top; i++) {
ret += stk[i];
}
return ret;
}