【BUAA 18级数据结构第二题】后缀表达式转中缀表达式&表达式计算

题面

• 【问题描述】
  从控制台输入一合法的后缀表达式，其中的运算符只包括+、-、*、/，运算数都是大于等于 0 的整数（除数不为零），按要求输出计算结果，或输出计算结果和相对应的中缀表达式。输出中缀表达式时只包含最少数目的圆括号（即在生成的中缀表达式中若去掉一对括号，则其将不能够转换回输入的后缀表达式）。输出计算结果时，小数点后保留两位，例如：10/3 的结果为 3.33
  假如输入的后缀表达式为：
  100 25 + 27 25 - / 248 + 201 -
  其相对应的中缀表达式为：
  (100+25)/(27-25)+248-201
  计算结果为 109.50。
• 【输入形式】
  首先从控制台输入一个合法的后缀表达式（长度不超过 200 个字符），其中的运算符、运算数之间都以一个空格分隔。然后在下一行输入一个整数 1 或 2 表示计算要求（1 表示只输出计算结果；2 表示输出对应的中缀表达式和计算结果）。
  【输出形式】
  若输入的计算要求为 1，则只将计算结果输出到控制台，小数点后保留两位；若输入的计算要求为 2，则先将后缀表达式对应的中缀表达式输出到控制台（其中添加的小括号都为英文小括号，表达式中不包含任何空白符），然后在下一行输出计算结果，小数点后保留两位。
  【样例 1 输入】
  100 25 + 27 25 - / 248 + 201 -
  1
  【样例 1 输出】
  109.50
  【样例 2 输入】
  100 25 + 27 25 - / 248 + 201 -
  2
  【样例 2 输出】
  (100+25)/(27-25)+248-201
  109.50
  【样例 1 和 2 说明】两样例输入了相同的后缀表达式。按计算要求，样例 1 只输出了计算结果；样例 2 输出了转换后的（包含最少括号的）中缀表达式和计算结果。按照后缀表达式的计算语义，当转换为中缀表达式时，前两个运算符连成的表达式100+25 和 27-25 都要加上小括号。
  【样例 3 输入】
  100 25 + 2 58 42 + * /
  2
  【样例 3 输出】
  (100+25)/(2*(58+42))
  0.63
  【样例 3 说明】按照后缀表达式的计算语义，生成中缀表达时表达式 2*(58+42)外应该加上小括号，否则两个表达式计算顺序不一致。
• 后缀转中缀算法提示：
  1、每步进行后缀表达式计算时，除了要保存计算结果外，还应保存对应的（以字符串形式表示的）运算符和中缀表达式。
  2、在进行后缀表达式计算时，当前运算符的优先级大于左运算对象运算符优先级，则生成对应的中缀表达式时左运算对象对应的中缀表达式应加括号；当前运算符的优先级大于或等于右运算对象运算符优先级时，则生成对应的中缀表达式时右运算对象对应的中缀表达式应加括号。其它情况则不用加括号。
  以样例 2 为例，在进行后缀表达式计算时：
  • 第一次进行’+‘运算时，左运算对象为 100，右为 25，运算结果为 125、运算符为’+‘、对应中缀表达式为 100+25；
  • 第二次进行’-‘运算时，左运算对象为 27，右为 25，运算结果为 2、运算符为’-‘、对应中缀表达式为 27-25；
  • 第三次进行’/‘运算时，左运算对象为 125、对应运算符为’+‘、对应中缀表达式为 100+25，由于’/‘优先级高于’+‘，因此生成对应中缀表达式时 100+25应加括号；右运算对象为 2、对应运算符为’-‘、对应中缀表达式为 27-25，由于’/‘优先级高于’-‘，因此生成对应中缀表达式时 27-25 也应加括号。该步运算结果为 62.5、运算符为’/'、对应中缀表达式为(100+25)/(27-25)；
  • 以此类推

思路分析

• 首先1情况很好实现，搞一个数据栈，从头开始读表达式，因为是后缀表达式，所以可以直接莫伊。即遇到数字就压入栈，遇到运算符就将栈顶的两个数字出栈进行运算，运算结果入栈。
• 情况2折磨我良久QAQ注意到算法提示中的描述，应该意识到这也是一个栈操作，区别在于栈内的元素是表达式，上述描述中左运算对象对应次栈顶元素，右运算对象对应栈顶元素，（单独的数也看作是一个表达式）每遇到运算符就将栈顶的两个元素弹出与运算符重新组合，组合结果入栈，这个过程和1是可以同步进行的。

总体规划有了，我们需要考虑的细节是：

1. 怎么加括号
2. 怎么组合新的表达式

• 加括号其实就是考虑先算谁，先算乘除再算加减肯定没问题，如果遇到优先级高一级的就直接加括号，但注意==大于或等于右运算对象运算符优先级==这一句中的等于，就是在问你从左往右算的时候先算谁（给谁加括号），优先级相等的情况有：–、++、±、**、//、*/ ，如果是前5种，那么运算顺序没有影响，所以不用加括号,而最后一种 5*6/3和(5*6)/3结果是不一样的，所以为了方便我们可以认为*的优先级低于/;
  这样只要判断表达式的运算符（表达式的运算符需要在每次组合完后更新）的优先级是否低于当前运算符，低于就加；
• 组合新表达式嘛，本蒻蒟笨笨的复制粘贴了一遍，懒得动脑子了
  基于这样的考虑，就可以有这样的一个表达式栈的结构，

   struct infix
  {
  	char item[MAXSIZE*2];
  	char flag;
  } ans_stack[MAXSIZE];

更多细节写注释里了~

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAXSIZE 205
struct infix
{
	char item[MAXSIZE*2];
	char flag;
} ans_stack[MAXSIZE];

double numSTACK[MAXSIZE];
int num[MAXSIZE],cnt;		/*这个num数组用来储存输入中的顺序，
							因为在表达式栈中为了简洁操作用'n'来代替数字，
							而后缀表达式转为中缀的过程中数字顺序没有变化，
							所以可以输出的时候遇到n直接从数学序列中对应输出*/
char opSTACK[MAXSIZE];
int numTOP,ansTop;

void Init()
{
	numTOP = -1;
	ansTop = -1;
}
void CAL(char op); //计算
int isLowerThan(char a,char b)//判断a的优先级是否小于b
{//判断优先级 注意*和/
	return ((a == '+' || a == '-') && (b == '*' || b == '/'))||(a=='*'&&b=='/');
}
void addBrackets(char flag, char s[],char c);
int main()
{
	Init();
	char in[300];
	char c;
	int i, aim, now = 0, flag = 0;
	gets(in);
	scanf("%d", &aim);
	for (i = 0; in[i]; i++)
	{
		c = in[i];
		if (c >= '0' && c <= '9')
		{//读入数字常用手段
			now *= 10, now += c - '0';
			flag = 1;
		}
		else if (c == ' ')
		{
			if (flag)//但注意如果没读入的话now一直是0 都入栈了 会有一些离谱的输出所以要判断有没有读数字
			{	numSTACK[++numTOP] =(double) now;
				ans_stack[++ansTop].item[0] = 'n';//用n代替数字
				ans_stack[ansTop].flag = '#';//如果是单个数字作为表达式就不用加括号，直接标记
				num[cnt++] = now;//作为输出的对应表
			}
			now = 0;
			flag = 0;
		}
		else
		{
			//先给左右运算对象加括号
			addBrackets(ans_stack[ansTop - 1].flag, ans_stack[ansTop - 1].item, c);
			addBrackets(ans_stack[ansTop].flag, ans_stack[ansTop].item, c);
			//然后组合，左 运算符 右连起来
			int len = strlen(ans_stack[ansTop - 1].item);
			ans_stack[ansTop - 1].item[len] = c;
			len++;
			for (int j = 0;ans_stack[ansTop].item[j];j++)
			{
				ans_stack[ansTop - 1].item[len++] = ans_stack[ansTop].item[j];
			}
			ans_stack[ansTop - 1].item[len] = '\0';
			ans_stack[ansTop - 1].flag = c;//重置当前表达式的运算符
			memset(ans_stack[ansTop].item, '\0', sizeof(ans_stack[ansTop].item));
			//注意出栈一定要清空数组
			ansTop--;
			CAL(c);
		}
	}
	cnt = 0;
	if (aim == 2)
	{
		for (int i = 0; ans_stack[0].item[i];i++)
		{
			if(ans_stack[0].item[i]=='n')
				printf("%d", num[cnt++]);
			else
				printf("%c", ans_stack[0].item[i]);
		}
		printf("\n");
	}
	printf("%.2lf", numSTACK[0]);
	return 0;
}
void addBrackets(char flag, char s[],char c)
{
	if(flag!='#'&&isLowerThan(flag,c))
	{
		int len = strlen(s);
		for (int j = len-1; j >= 0;j--)
			s[j + 1] = s[j];
		s[0] = '(';
		s[len + 1] = ')';
		s[len + 2] = '\0';
	}
	return;
}
void CAL(char op)
{
	if (op == '*')
		numSTACK[numTOP - 1] = numSTACK[numTOP - 1] * numSTACK[numTOP];
	else if (op == '/')
		numSTACK[numTOP - 1] = numSTACK[numTOP - 1] / numSTACK[numTOP];
	else if (op == '+')
		numSTACK[numTOP - 1] = numSTACK[numTOP - 1] + numSTACK[numTOP];
	else if (op == '-')
		numSTACK[numTOP - 1] = numSTACK[numTOP - 1] - numSTACK[numTOP];
	numTOP--;
}