济南seo网站建站,网站建设起到计划和指导作用,杭州ppt设计公司,成立一个网站平台要多少钱
后缀表达式
题目描述
后缀表达式是指这样的一个表达式#xff1a;式中不使用括号#xff0c;运算符号放在两个运算数之后#xff0c;所有计算按运算符号出现的顺序#xff0c;严格地自左而右进行#xff08;不用考虑运算符的优先级#xff09; 如#xff1a;3*(5-…
后缀表达式
题目描述
后缀表达式是指这样的一个表达式式中不使用括号运算符号放在两个运算数之后所有计算按运算符号出现的顺序严格地自左而右进行不用考虑运算符的优先级 如3*(5-2)7对应的后缀表达式为3 5 2 - * 7 。’’为表达式的结束符号。 注运算过程中请使用long long进行运算。
关于输入
多行每行一个用空格分割的后缀表达式。保证表达式长度不超过1000个字符。 表达式中可能出现整数 - * /四种运算符以及。
关于输出
输出多行为对应表达式的值。 如果在运算过程中出现除0那么输出NaN。
例子输入
3 5 2 - * 7
例子输出
16
解题分析
这个问题中我们需要计算后缀表达式的值。后缀表达式是一种没有括号运算符放在两个操作数之后的表达式所有计算按照运算符出现的顺序严格地从左到右进行。
解决这个问题的关键在于理解后缀表达式的计算方式以及如何利用栈数据结构来进行计算。
我们使用一个栈来存储数字然后遍历输入的字符串。如果遇到的是数字我们就把它压入栈中。如果遇到的是运算符我们就从栈顶弹出两个元素进行相应的运算然后把结果再压回栈中。这样当我们遍历完整个字符串后栈顶的元素就是整个表达式的计算结果。
可以用一个数组stack来模拟栈top变量用来表示栈顶的位置。push函数用来把一个元素压入栈pop函数用来弹出栈顶的元素。
在main函数中我们首先读入一行输入然后遍历这个字符串。如果遇到的是数字我们就把它转换成整数并压入栈中。如果遇到的是运算符我们就弹出栈顶的两个元素进行相应的运算然后把结果压回栈中。如果遇到的是’我们就直接输出栈顶的元素然后清空栈。
在处理除法时我们需要注意除数不能为0。如果除数为0我们就直接输出NaN然后跳出循环。
这个算法的时间复杂度为O(n)其中n为输入字符串的长度空间复杂度为O(n)其中n为输入字符串中数字的个数。
代码实现
#include stdio.h
#include stdlib.h
#include string.hlong long stack[1005];
int top-1;void push(long long a){stack[top]a;
}long long pop(){return stack[top--];
}int main(){char input[1005];long long a,b;while(fgets(input,1005,stdin)){int i0;while(istrlen(input)){if(input[i]0 input[i]9){long long num0;while(istrlen(input) input[i]0 input[i]9){num*10;numinput[i]-0;i;}push(num);}else if(input[i]){apop(); bpop();push(ba);i;}else if(input[i]-){apop(); bpop();push(b-a);i;}else if(input[i]*){apop(); bpop();push(b*a);i;}else if(input[i]/){apop(); bpop();if(a0){printf(NaN\n);break;}push(b/a);i;}else if(input[i]){printf(%lld\n,pop());top-1;break;}else{i;}}}return 0;
}
代码详细解释
当然可以让我们更详细地分析这段代码
首先我们定义了一个全局的栈stack和一个栈顶指针top。这个栈用来存储后缀表达式中的数字栈顶指针用来表示当前栈顶的位置。
long long stack[1005];
int top-1;接下来我们定义了两个操作栈的函数push和pop。push函数用来将一个元素压入栈pop函数用来弹出栈顶的元素。
void push(long long a){stack[top]a;
}long long pop(){return stack[top--];
}在main函数中我们首先读入一行输入然后开始遍历这个字符串。
char input[1005];
long long a,b;
while(fgets(input,1005,stdin)){int i0;while(istrlen(input)){如果遇到的是数字我们就把它转换成整数并压入栈中。
if(input[i]0 input[i]9){long long num0;while(istrlen(input) input[i]0 input[i]9){num*10;numinput[i]-0;i;}push(num);
}如果遇到的是运算符我们就弹出栈顶的两个元素进行相应的运算然后把结果压回栈中。
else if(input[i]){apop(); bpop();push(ba);i;
}
else if(input[i]-){apop(); bpop();push(b-a);i;
}
else if(input[i]*){apop(); bpop();push(b*a);i;
}
else if(input[i]/){apop(); bpop();if(a0){printf(NaN\n);break;}push(b/a);i;
}如果遇到的是’我们就直接输出栈顶的元素然后清空栈。
else if(input[i]){printf(%lld\n,pop());top-1;break;
}对于其他字符我们直接忽略。
else{i;
}最后当我们遍历完整个字符串后我们就可以得到后缀表达式的计算结果。
这个算法的时间复杂度为O(n)其中n为输入字符串的长度空间复杂度为O(n)其中n为输入字符串中数字的个数。
