NYOJ467 中缀式变后缀式 【栈】
后缀 中缀
2023-09-14 09:08:54 时间
中缀式变后缀式
时间限制:1000 ms | 内存限制:65535 KB
难度:3
- 描写叙述
-
人们的日常习惯是把算术表达式写成中缀式,但对于机器来说更“习惯于”后缀式。关于算术表达式的中缀式和后缀式的论述一般的数据结构书都有相关内容可供參看。这里不再赘述,如今你的任务是将中缀式变为后缀式。
- 输入
-
第一行输入一个整数n,共同拥有n组測试数据(n<10)。
每组測试数据仅仅有一行。是一个长度不超过1000的字符串,表示这个运算式的中缀式,每一个运算式都是以“=”结束。这个表达式里仅仅包括+-*/与小括号这几种符号。当中小括号能够嵌套使用。数据保证输入的操作数中不会出现负数。
数据保证除数不会为0 - 输出
- 每组都输出该组中缀式对应的后缀式,要求相邻的操作数操作符用空格隔开。
- 例子输入
-
2 1.000+2/4= ((1+2)*5+1)/4=
- 例子输出
-
1.000 2 4 / + = 1 2 + 5 * 1 + 4 / =
- 来源
- 数据结构
- 上传者
-
mix_math
题意:...
题解:须要两个栈,一个是符号sta栈。一个是后缀式out栈,每次在buf中读取字符时。假设是数字或者‘.’,则直接存到out栈里,假设是别的字符。则将它放入sta栈,前提是保证sta栈内优先级严格递减。
#include <stdio.h> #include <string.h> #include <ctype.h> #define maxn 1010 char buf[maxn], out[maxn << 1]; char sta[maxn]; // 符号栈 int id, id2; int getLevel(char ch) { switch(ch) { case '(': return 0; case '+': case '-': return 1; case '*': case '/': return 2; } } void check(char ch) { int level; if(ch == '(') sta[id2++] = ch; else if(ch == ')') { while(sta[id2-1] != '(') { out[id++] = sta[--id2]; out[id++] = ' '; } --id2; } else { while(id2 && getLevel(sta[id2-1]) >= getLevel(ch)) { out[id++] = sta[--id2]; out[id++] = ' '; } sta[id2++] = ch; } } void solve() { int i, sign; id = id2 = 0; for(i = sign = 0; buf[i] != '='; ++i) { if(isdigit(buf[i]) || buf[i] == '.') { out[id++] = buf[i]; sign = 1; } else { if(sign) { out[id++] = ' '; sign = 0; } check(buf[i]); } } while(id2) { if(sign) { out[id++] = ' '; sign = 0; } out[id++] = sta[--id2]; out[id++] = ' '; } out[id] = '\0'; printf("%s=\n", out); } int main() { // freopen("stdin.txt", "r", stdin); int t; scanf("%d", &t); while(t--) { scanf("%s", buf); solve(); } return 0; }
相关文章
- 查询后缀字符串出现的次数
- JavaScript : 获取文件名后缀
- 数据结构Java实现06----中缀表达式转换为后缀表达式
- 批处理:遍历输出指定后缀格式的文件名.bat
- 技巧两种:LINUX删除指定后缀文件及PYTHON更改屏幕字色
- 前缀中缀后缀表达式
- 前缀中缀后缀表达式
- 流式计算框架Storm编程案例:实时给手机品牌转大写并加上时间戳后缀代码示例
- Atitti. 语法树AST、后缀表达式、DAG、三地址代码
- python获取文件的名字和后缀
- 后缀数组(模版测试中)
- 【Android Gradle 插件】BuildType 编译类型配置 ① ( BuildType 编译类型简介 | BuildType#applicationIdSuffix 包名后缀配置 )
- 中缀表达式转后缀表达式
- 有效的域名后缀列表