LeedCode刷题笔记-计算器
题目描述
给定一个包含正整数、加(+)、减(-)、乘(*)、除(/)的算数表达式(括号除外),计算其结果。
表达式仅包含非负整数,+, - ,*,/ 四种运算符和空格 。 整数除法仅保留整数部分。
示例 1:
输入: “3+2*2”
输出: 7
示例 2:
输入: " 3/2 "
输出: 1
示例 3:
输入: " 3+5 / 2 "
输出: 5
说明:
你可以假设所给定的表达式都是有效的。
请不要使用内置的库函数 eval。
解题代码
int calculate(char* s)
{
/* 记录上一个运算符号, 当新的运算符到来时 */
/* 运算上个运算符, 加减运算, 数字进栈 */
/* 乘除运算时, 需要进行运算后进栈 */
int len = strlen(s);
int * stack = (int *)malloc(sizeof(int) * len);
int top = 0;
char oper = '+';
int ret = 0;
int num = 0;
int i;
char ch;
/* 对字符串逐一处理 */
for(i = 0; i <=len; i++)
{
ch = s[i];
if(ch == ' ')
{
/* 去掉空格 */
continue;
}
if(ch >= '0' && ch <= '9')
{
/* 两位及以上数字的获取如123 */
num = num * 10 + (ch - '0');
}
else
{
if(oper == '+')
{
stack[top++] = num;
}
else if(oper == '-')
{
stack[top++] = -num;
}
else if(oper == '*')
{
stack[top - 1] = stack[top - 1] * num;
}
else if(oper == '/')
{
stack[top - 1] = stack[top - 1] /num;
}
oper = ch;
num = 0;
}
}
/* 栈非空是,栈元素相加 */
while(top > 0)
{
ret += stack[--top];
}
return ret;
}
总结
- 需要注意的是两位数的获取,不能看例子没有,就不去考虑,使用
num = num * 10 + (ch - '0');
加循环判断来得到字符串中的两位及以上数字 - 还有就是对于先乘除再加减,这里使用的是栈容器去解决,和数据结构中的后缀表达式是类似的
- 对于加减的数字,直接转化为+,存储之后最后再计算
- 对于乘除的数字,都是计算之后再入栈,如
if(oper == '/') { stack[top - 1] = stack[top - 1] /num; }