1
表达式转换 - 中缀转后缀表达式后计算 - 数据结构与算法
作者:阿锋
- 2022 年 8 月 15 日 湖北
本文字数:2825 字
阅读完需:约 9 分钟
前言
🚀 个人主页:阿阿阿阿锋的主页_CSDN🔥 有问题欢迎指出,🔥 希望能和大家一起加油,一起进步!
🌍 另外,给大家推荐一款神器:《牛客网》🌍 无论是面试,还是刷题学习,都非常好用。而且调试在线编程题时,是可以对比测试数据对应的正确输出的。
@[TOC]
问题
一个==计算中缀表达式==的算法题
40分,其余六个测试点都显示"read(ASCII 13)"
我的代码现在一直只能过第1、6、7、8这四个测试集,
查看测试集显示错误信息:
“Wrong Answer.wrong answer On line 1 column 25, read (ASCII 13), expected +.”
复制代码
题目链接:表达式转换-洛谷
我查了(ASCII 13)是回车键,但是我又能过四个测试集,为什么输出会有回车键的问题呢?
谁能救救我啊?万分感谢!
下面是我的代码(可能有点乱,抱歉):
/*long long
1)输入数字是单个数字
2)输入没有负数 */
#include<iostream>
#include<cstdio>
#include<stack>
using namespace std;
const int max0 = 500;
stack<char> s; //计算后缀表达式用
long long get_num(); //从栈中返回一个整型数字
bool compare_sign(char big, char small); //比较两个(四则运算符)运算符的优先级
void change(char str[]); //给新转化出来的后缀表达式 操作数 加分隔符'.'
void out_bds(char str[], int i, stack<char> ss);//输出中间产物表达式
int main() {
char a[max0]{}; //后缀表达式
int ac(0); //迭代a
stack<char> sign; //符号栈
char m[max0]{}; //待处理的中缀表达式
char ch(0);
for(int i = 0; i < max0; ++i){
ch = getchar();
if(ch == '\n') break;
m[i] = ch; }
//--------------------一、中缀表达式转后缀表达式
for(int i = 0; i < max0 && m[i] != '\0'; i++) { //读取中缀表达式并开始转换
if('0' <= m[i] && m[i] <= '9') { //遇到操作数,直接加入后缀表达式
a[ac++] = m[i]; }
else if(m[i] != '(' && m[i] != ')') {
while(!sign.empty() && compare_sign(sign.top(), m[i])) {
a[ac++] = sign.top(); //遇到运算符,出栈优先级不小于它的运算符加入表达式,直到栈空或遇到'('
sign.pop(); }
sign.push(m[i]); } //然后自己入栈
else if(m[i] == '(') {
sign.push(m[i]); }
else if(m[i] == ')') { //遇到')',出栈加入表达式直到'('
while(sign.top() != '(') {
a[ac++] = sign.top();
sign.pop(); }
sign.pop(); }}
while(!sign.empty()) { //出栈所有剩余运算符
a[ac++] = sign.top();
sign.pop(); }
change(a);
out_bds(a, 0, s);
//--------------------二、计算后缀表达式
char t(0); ac = 0;
while(true) {
t = a[ac++]; //入栈
if(t == '@') {s.pop();break;}
s.push(t);
if(t == '+' || t == '-' || t == '*' || t == '/' || t == '^') { //见运算符
s.pop(); //出栈运算符
long long d(0), b(0); //出栈两个数字为int型
s.pop(); d = get_num();
s.pop(); b = get_num();
long long result(1); //计算
if(t == '+') result = b + d;
else if(t == '-') result = b - d;
else if(t == '*') result = b * d;
else if(t == '/') result = b / d;
else if(t == '^') {
for(int i = 0; i < d; ++i)
result *= b; }
if(result < 0) {s.push('0'); result = -result;}
stack<char> c; //结果转为char型再入栈
if(result == 0) {s.push('0');}
while(result != 0) {
c.push((char)(result % 10 + '0'));
result /= 10; }
while(!c.empty()) {
s.push(c.top());
c.pop(); }
s.push('.');
out_bds(a, ac, s); }}
return 0; }
//----------------------------------------
//只考虑了表达式转换过程中可能发生的优先级比较
bool compare_sign(char big, char small) {
if(big == '+' || big == '-') {
if(small == '+' || small == '-') return true; }
else if(big == '*' || big == '/' || big == '^') {
if(small != '(' && small != '^') return true; }
return false; }
//----------------------------------------
//从char型栈中读取出一个int型操作数
long long get_num() {
long long sum(0);
char t(0);
for(long long i = 1; s.top() != '.'; i *= 10) { //i也是必须开long long的
t = s.top();
sum += (long long)(s.top() - '0') * i;
s.pop();
if(s.empty()) break; }
if(t == '0') sum = -sum;
return sum; }
//----------------------------------------
//从char型栈中读取出一个int型操作数;out_bds()的配套
long long get_num(stack<char> &ss) {
long long sum(0);
char t(0);
for(long long i = 1; ss.top() != '.'; i *= 10)
{ t = ss.top();
sum += (long long)(ss.top() - '0') * i;
ss.pop();
if(ss.empty()) break; }
if(t == '0') sum = -sum;
return sum; }
//----------------------------------------
//给新转化出来的后缀表达式 操作数 加分隔符'.'
void change(char str[]) {
char t[max0]{};
int tc(0);
for(int i = 0; str[i] != '\0'; i++) {
if('0' <= str[i] && str[i] <= '9') {
t[tc++] = str[i];
t[tc++] = '.'; }
else t[tc++] = str[i]; }
for(int i = 0; t[i] != '\0'; i++)
str[i] = t[i];
str[tc] = '@'; } //表达式结束符
//----------------------------------------
//输出中间产物表达式,从str[i]开始;参数建立了一个副本栈,不担心原s改变
void out_bds(char str[], int i, stack<char> ss) {
stack<long long> t; //中转站
while(ss.empty() == 0) {
if(ss.top() == '.')
ss.pop();
t.push(get_num(ss)); }
while(t.empty() == 0) {
cout << t.top() << " ";
t.pop(); }
for( ; str[i] != '\0'; i++) {
if(str[i] != '.' && str[i] != '@')
cout << str[i] << " "; }
cout << endl; }
/*
测试集
8-(3+2*6)/5+4
9+(9^8+(9^8+(9^8+(9^8))))
*/
复制代码
程序运行:
经验总结
注意创建的==数组大小==,题目说输入字符串长度不超过 100,但是表达式计算过程中的==中间结果==是可能超过 100 的。
注意不要==变量名冲突==。
仔细审题,有些坑很细,如:计算过程总数字==不超过==2^31^,但是可能等于,那 int 类型就不够了。
如果==重载==了函数,修改其中一个时可能其它的也需要修改
输出==格式==其实挺烦的,有时题目不会说很清楚,甚至就必须有行末空格。
划线
评论
复制
发布于: 刚刚阅读数: 3
版权声明: 本文为 InfoQ 作者【阿锋】的原创文章。
原文链接:【http://xie.infoq.cn/article/d2c6631fd5b747aac8fda0379】。
本文遵守【CC-BY 4.0】协议,转载请保留原文出处及本版权声明。
阿锋
关注
还未添加个人签名 2022.08.09 加入
还未添加个人简介
评论