nyoj 467 中缀式变后缀式 (栈)
2024-09-01 17:02:19
中缀式变后缀式
时间限制: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 / =/**
分析:
Ⅰ、建立stack (放操作符)、queue (放操作结果)
Ⅱ、isdigit (s [i]) || s [i] == '.' 直接 queue.push (s [i])
Ⅲ、s [i] == '(' 入栈
Ⅳ、s [i] == ')' 将 '(' 以上的所有运算符出栈 (入队列),最后将 '(' 出栈
Ⅴ、遇到操作符判断其和栈顶元素的关系
Ⅴ(①)、如果 priority (stack.top()) >= priority (s [i]), 出栈 (入队列)
Ⅵ、将stack中除 '#' 以外所有的运算符出栈(入队列)
**/核心代码:
/**
for (int i = 0; i < len; ++ i) {
if (isdigit (s [i]) || s [i] == '.')
que.push (s [i]);
else if (s [i] == '(')
sta.push (s [i]);
else if (s [i] == ')') {
char c = sta.top ();
while (c != '(') {
que.push (c);
que.push (' ');
sta.pop ();
c = sta.top ();
}
sta.pop ();
} else {
char c = sta.top ();
while (priority (c) >= priority (s [i])) {
que.push (c);
que.push (' ');
sta.pop ();
c = sta.top ();
}
} if (isdigit (s [i]) && (s [i + 1] == '/' || s [i + 1] == '+' ||
s [i + 1] == '-' || s [i + 1] == '*' || s [i + 1] == '=' || s [i + 1] == ')')) {
que.push (' ');
}
}
**/C/C++代码实现(AC):
#include <bits/stdc++.h> using namespace std; int priority (char c) {
if (c == '/' || c == '*') return ;
if (c == '+' || c == '-') return ;
if (c == '=') return ;
return ;
} int main () {
int T;
scanf ("%d", &T);
while (T --) {
char s [];
int len;
queue <char> que;
stack <char> sta;
sta.push ('#'); getchar ();
scanf ("%s", &s[]);
len = strlen (s); for (int i = ; i < len; ++ i) {
if (isdigit (s [i]) || s [i] == '.') {
que.push (s [i]);
} else if (s [i] == '(') {
sta.push (s [i]);
} else if (s [i] == ')') {
char c = sta.top ();
while (c != '(') {
que.push (c);
que.push (' '); // 运算符间空格
sta.pop ();
c = sta.top ();
}
sta.pop ();
} else {
char c = sta.top ();
while (!sta.empty() && priority (c) >= priority (s [i])) {
que.push (c);
que.push (' '); // 运算符间空格
sta.pop ();
c = sta.top ();
}
sta.push (s [i]);
} if (isdigit (s [i]) && (s [i + ] == '/' || s [i + ] == '+' ||
s [i + ] == '-' || s [i + ] == '*' || s [i + ] == '=' || s [i + ] == ')')) {
// 数字与运算符间空格
que.push (' ');
}
}
while (!sta.empty () && sta.top () != '#') {
que.push (sta.top ());
sta.pop ();
}
while (!que.empty ()) {
printf ("%c", que.front ());
que.pop ();
}
printf ("\n");
}
return ;
}
最新文章
- Log4j 用法
- [zz]谱聚类
- OAF_开发系列16_实现OAF与XML Publisher整合
- 1334: [Baltic2008]Elect
- jquery概要--基础02
- Linked List Cycle II
- 如何使用javascript书写递归函数
- Java并发编程:线程和进程的创建(转)
- Linux能力(capability)机制的继承
- 同步Flex Chart的数据提示
- bzoj 2286 [Sdoi2011]消耗战 虚树+dp
- ES(二): Build ES Cluster on Azure VM
- sqlserver-4064
- Java开发知识之Java中的Map结构
- mongoDB 文档概念
- python 在.py文件中调用其他.py内的函数
- php使用ffmpeg向视频中添加文字字幕
- [精彩] 关于DB2的内存分配
- ubuntu下编译源码 make 出现 make: &#39;Makefile&#39; is up to date.
- Java 泛型通配符上限和通配符下限