请写一个整数计算器，支持加减乘三种运算和括号。
数据范围：
，保证计算结果始终在整型范围内
要求：空间复杂度： )
，时间复杂度
[编程题]表达式求值
int GetInt(char **s) {
int res=0;
bool GetInt = false;
while((**s)!=0) {
if((**s)>='0' && (**s)<='9') {
res *=10;
res += ((**s)-'0');
(*s)++;
GetInt = true;
}
else {
if(GetInt)
break;
else
(*s)++;
}
}
return res;
}
int bracketLen(char *s) {
int len=0;
if(s[0]!='(')
return 0;
else {
s++;
while(1) {
char c = s[len];
if(c=='(') {
len += bracketLen(s+len)+2;
continue;
}
else if(c==')' || c==0)
break;
len++;
}
}
return len;
}
int solve(char* s ) {
#define push(a) stack[pointStack++] = a
#define pop() stack[--pointStack]
int stack[100]={0}, pointStack=0;
int res=0;
char *p=s;
bool firstFlag = true;
while(*p) {
if(*p=='(') {
char *buffer;
int BKval;
int BKLen = bracketLen(p);
buffer = (char*)malloc(BKLen+1);
strncpy(buffer, p+1, BKLen);
buffer[BKLen] = 0;
BKval = solve(buffer);
if(!firstFlag) {
if(*(p-1)=='-')
push(-BKval);
else if(*(p-1)=='+')
push(BKval);
else if(*(p-1)=='*')
push(pop()*BKval);
}
else
push(BKval);
firstFlag = false;
p += BKLen+strlen("()");
}
else if(*p>='0' && *p<='9') {
if(!firstFlag) {
if(*(p-1)=='-')
push(-GetInt(&p));
else if(*(p-1)=='+')
push(GetInt(&p));
else if(*(p-1)=='*')
push(pop()*GetInt(&p));
}
else
push(GetInt(&p));
firstFlag = false;
}
else if(*p=='+' || *p=='-') {
while(pointStack)
res += pop();
p++;
}
else if(*p=='*' || *p==')')
p++;
}
while(pointStack) {
res += pop();
}
return res;
}
编辑于 2024-03-20 17:20:41
回复(0)
用了递归。
#include <string.h>
//返回字符串长度
int sizestr(char* s) {
int i = 0;
while (s[i] != '\0')
i++;
return i + 1;
}
int solve(char* s) {
// write code here
int data[100], sign[100];
int no = 0, no_s = 0;
for (int i = 0;s[i] != '\0';i++) {
if (s[i] == '(')
data[no++] = solve(s + i + 1);//遇到'('时递归
if (s[i] == ')') {
memcpy(s, s + i + 1, sizestr(s + i + 1));//函数退出时，清理已经计算过的表达式，防止重复计算
break;
}
if (s[i] >= '0' && s[i] <= '9') {
int num = 0;
while (s[i] >= '0' && s[i] <= '9') {//字符数转int，存入数组
num = num * 10 + s[i] - '0';
i++;
}
i--;
data[no++] = num;
}
if (s[i] == '*') {//乘法可以先计算，先算后存
i++;
if (s[i] >= '0' && s[i] <= '9') {
int num = 0;
while (s[i] >= '0' && s[i] <= '9') {
num = num * 10 + s[i] - '0';
i++;
}
i--;
data[no - 1] *= num;//计算结果覆盖存入
}
else if (s[i] == '(')//出现'*('时的情况
data[no - 1] *= solve(s + i + 1);//同样先计算括号里的
}
else if (s[i] == '+') {//加减法，先存再算，此时只要存符号，数字上面存了
sign[no_s++] = s[i];
}
else if (s[i] == '-') {
sign[no_s++] = s[i];
}
}
for (int i = 0, j = 0;i < no_s;i++) {//计算
if (sign[i] == '+') {
data[j + 1] = data[j] + data[j + 1];
data[j++] = 0;
}
else if (sign[i] == '-') {
data[j + 1] = data[j] - data[j + 1];
data[j++] = 0;
}
}
return data[no - 1];
}
发表于 2023-07-12 19:24:03
回复(0)
/*
支持加减乘括号运算，"2*(3+4)"
1.建立两个栈，一个存数字，一个存运算符；
2.对于数字直接进栈，对于运算符，当前运算符大于栈顶运算符时入栈，否则从数栈中弹出两个数进行运算。
3.注意：字符串遍历完，同时运算符栈为空时，计算才结束；对于数字要循环读取字符直至运算符；
*/
int isOperator(char c){
if(c=='(' || c==')' || c=='+' || c=='-' || c=='*')
return 1;
else
return 0;
}
/*
运算符优先级比较一定考虑哪个在左边哪个在右边，
a ? b （a在左边，b在右边，即a是已经进栈字符,b是当前字符）
a,b ( ) + - *
( < = < < <
) ? > > > >
+ < > > > <
- < > > > <
* < > > > >
*/
char getCmp(char a,char b){//a在左边，b在右边
if(a=='('){
if(b==')')
return '=';
return '<';
}else if(a==')'){
return '>';
}else if(a=='+' || a=='-'){
if(b=='(' || b=='*')
return '<';
return '>';
}else{//a=='*'
if(b=='(')
return '<';
return '>';
}
}
int cal(int a,int b,char op){
if(op=='+')
return a+b;
else if(op=='-')
return a-b;
else
return a*b;
}
int solve(char* s ) {
int stk_num[100];
char stk_op[100],op;
int top_num=0,top_op=0,i=0,a,b;
while(s[i]!='\0'|| top_op!=0){
if(s[i]!='\0' && isOperator(s[i])==1){//是运算符
if(top_op==0 || getCmp(stk_op[top_op-1],s[i])=='<'){//当前运算符优先级较大，压栈
stk_op[top_op++]=s[i];
i++;
}else if(getCmp(stk_op[top_op-1],s[i])=='>'){//弹栈，进行运算
op=stk_op[--top_op];
b=stk_num[--top_num];
a=stk_num[--top_num];
stk_num[top_num++]=cal(a,b,op);//计算后再压栈
}else{//消掉左右括号
top_op--;
i++;
}
}else if(s[i]=='\0'){//字符全部压入栈，弹栈
while(top_op!=0){//内循环弹运算符栈，不用走大循环
b=stk_num[--top_num];
a=stk_num[--top_num];
op=stk_op[--top_op];
stk_num[top_num++]=cal(a,b,op);//计算后再压栈
}
}else{//是操作数
int x=0;
while(s[i]!='\0' && isOperator(s[i])!=1){//循环读取n位数，构成一个操作数
x=x*10+s[i]-'0';
i++;
}
stk_num[top_num++]=x;
}
}//while
return stk_num[0];
}
发表于 2023-04-02 12:02:56
回复(0)
拿C写这东西
char* noBlank(char *s){
char *p = (char *)malloc(sizeof(char) * (strlen(s)+1));
strcpy(p, s);
int len = strlen(s);
for(int i=0; i<len; i++){
if(*(p+i) == ' '){
for(int j=i; j<len; j++){
*(p+j) = *(p+j+1);
}
len--;
i--;
}
}
return p;
}
int solve(char* s ) {
// write code here
char *p;
char *q;
int t;
int len = strlen(s);
int quelen = 10;
p = noBlank(s);
int stackInt[quelen];
memset(stackInt, 0, sizeof(stackInt));
char stackChar[quelen];
memset(stackChar, 0, sizeof(stackChar));
int lock = 0;
int up = 0, top = 0;
while(*p != '\0'){
if(48 <= *p && *p <= 57){ //如果是数字
stackInt[up] = stackInt[up]*10 + (*p - 48);
lock = 1;
}
else{
if(stackChar[top-1] != 0){
if(*p == ')'){
t = top;
while(stackChar[t-1] != '('){
switch (stackChar[t-1]){
case '+':
stackInt[up-2] = stackInt[up-2] + stackInt[up-1];
stackInt[--up] = 0;
break;
case '-':
stackInt[up-2] = stackInt[up-2] - stackInt[up-1];
stackInt[--up] = 0;
break;
case '*':
stackInt[up-2] = stackInt[up-2] * stackInt[up-1];
stackInt[--up] = 0;
break;
case '(':
break;
}
t--;
top--;
}
top--;
}
else if(*p == '('){
stackChar[top++] = *p;
}
else{
switch (*p){
case '*':
switch (stackChar[top-1]){
case '(':
stackChar[top++] = *p;
break;
case '*':
stackInt[up-2] = stackInt[up-2] * stackInt[up-1];
stackInt[--up] = 0;
stackChar[top-1] = *p;
break;
case '+':
stackChar[top++] = *p;
break;
case '-':
stackChar[top++] = *p;
break;
}
break;
case '+':
switch (stackChar[top-1]){
case '(':
stackChar[top++] = *p;
break;
case '*':
stackInt[up-2] = stackInt[up-2] * stackInt[up-1];
stackInt[--up] = 0;
stackChar[top-1] = *p;
break;
case '+':
stackInt[up-2] = stackInt[up-2] + stackInt[up-1];
stackInt[--up] = 0;
stackChar[top-1] = *p;
break;
case '-':
stackInt[up-2] = stackInt[up-2] - stackInt[up-1];
stackInt[--up] = 0;
stackChar[top-1] = *p;
break;
}
break;
case '-':
switch (stackChar[top-1]){
case '(':
stackChar[top++] = *p;
break;
case '*':
stackInt[up-2] = stackInt[up-2] * stackInt[up-1];
stackInt[--up] = 0;
stackChar[top-1] = *p;
break;
case '+':
stackInt[up-2] = stackInt[up-2] + stackInt[up-1];
stackInt[--up] = 0;
stackChar[top-1] = *p;
break;
case '-':
stackInt[up-2] = stackInt[up-2] - stackInt[up-1];
stackInt[--up] = 0;
stackChar[top-1] = *p;
break;
}
break;
}}
}
else
stackChar[top++] = *p;
}
if(!(48 <= *(p+1) && *(p+1) <= 57) && lock == 1){
up++;
lock = 0;
}
p++;
}
while(top != 0){
switch (stackChar[top-1]){
case '+':
stackInt[up-2] = stackInt[up-2] + stackInt[up-1];
stackInt[--up] = 0;
break;
case '-':
stackInt[up-2] = stackInt[up-2] - stackInt[up-1];
stackInt[--up] = 0;
break;
case '*':
stackInt[up-2] = stackInt[up-2] * stackInt[up-1];
stackInt[--up] = 0;
stackChar[top-1] = *p;
break;
}
top--;
}
return stackInt[0];
}
发表于 2022-07-29 18:51:38
回复(1)
问题信息
难度：
4条回答
1953收藏
6322浏览
通过挑战的用户
查看代码-
2022-09-16 16:05:14
-
2022-09-16 15:14:19
-
2022-09-16 15:06:25
-
2022-09-16 13:45:22 -
2022-09-16 11:57:24
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K2座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
