[2018.04.17][水][日志][8][#207][计算表达式的值][calculate][->][栈][代码智熄]

[背景]

  近日VHOS再次把第二页的题目刷完了，小小庆祝一下~

然后，当我发现线性表只有一道题被我AC时，我惊奇发现，我来到了栈的世界~

[题干][#207 计算表达式的值]

题目描述
    小明在你的帮助下，破译了Ferrari设的密码门，正要往前走，突然又出现了一个密码门。
门上有一个算式，其中只有“(”、“)”、“0-9”、“+”、“-”、“*”、“/”、“^”，求出的值就是密码。小明的数学学得不好，还需你帮他的忙。(“/”用整数除法)

输入格式
    只有一行是一个算式(算式长度<=30)。

输出格式
    对于每组数据，输出算式的值(所有数据在2^31-1内)。

样例数据
input
1+(3+2)*(7^2+6*9)/(2)

output
258

时间限制：1s
1s
空间限制：256MB

256MB

[分析]

这道题ZTMD是坑人坑到极点，虽然题干不长，看着也很水，实际上却有一些VHOS所不知道的代码所在。

  首先，我去网上搜索了一下，发现我们必须把中缀表达式（就如输入那样所示）虚伪成后缀表达式（逆波兰表达式）

    在我们将中缀表达式转换为后缀表达式之前，我们先来说说对于一个后缀表达式，我们是如何计算的。首先我们确定一点，计算后缀表达式需要一个栈，而且计算过程需要的是一个操作数栈，计算顺序就是：将后缀表达式从左到右依次遍历，如果当前元素为数字则入（操作数）栈，如果为操作符，则pop出栈顶两个元素（第一次pop出的是右操作数，第二次pop出的是左操作数）进行运算，然后将计算结果再次入栈，直至表达式结束，此时操作数栈内理应只剩一个元素即表达式结果。

　　比如，与a+b等价的ab+，我们遇到a，入栈

　　

　　遇到b，入栈

　　

　　遇到'+'，pop得到b作为右操作数，再pop得到a作为左操作数（谁左谁右需要注意，减法、除法时弄反了结果将是错的），进行a+b运算，得出结果入栈

　　

　　然后表达式到了结尾，所以pop出栈内唯一元素即结果。

　　再比如，与a+b*c等价的abc*+，我们遇到a、b、c，依次入栈

　　

　　遇到'*'，pop出c作为右操作数，pop出b作为左操作数，进行b*c运算后将结果入栈

　　

　　遇到'+'，pop出b*c的结果（假设为d）作为右操作数，pop出a作为左操作数，进行a+d运算，然后将结果入栈

　　

　　此时表达式结束，栈内只剩一个元素，即表达式结果。而且很显然的，这个结果是对的！

　　至此，我们已经确定了两件事情：

　　1.中缀表达式必然存在后缀表达法

　　2.后缀表达式不存在优先级问题，只需利用栈进行“从左至右依次计算”即可

　　为了强化对后缀表达式计算方法的记忆（因为后面还有不少篇幅），我们再说一次后缀表达式的计算方法，就是：将后缀表达式从左到右依次遍历，如果当前元素为数字则入（操作数）栈，如果为操作符，则pop出栈顶两个元素（第一次pop出的是右操作数，第二次pop出的是左操作数）进行运算，然后将计算结果再次入栈，直至表达式结束，此时操作数栈内理应只剩一个元素即表达式结果。

但是...这个东西特别的虚伪，还带有（）...运算符,所以.,...

思路：

所包含的运算符有‘+’，‘-’，‘*’，‘/’，‘（’，‘）’...

[1]建立两个栈，一个用来存储操作数，另一个用来存储运算符, 开始时在运算符栈中先压入‘/0’，一个表达式的结束符。

[2]然后从左至右依次读取表达式中的各个符号（操作数或者运算符）；

[3]如果读到的是操作数直接存入操作数栈；

[4]如果读到的是运算符，则作进一步判断：

    [1]若读到的是‘/0’结束符，而且此时运算符栈的栈顶元素也是‘/0’结束符，则运算结束，输出操作数栈中的元素即为最后结果。

    [2]若读到的是‘（’或者读到的运算符的优先级比目前的运算符栈中的栈顶元素的优先级高，则将运算符直接存入运算符栈，继续读表达式中的下一个符号，重复步骤（3）和（4）；

    [3]若读到的是‘)’,而且此时运算符栈的栈顶元素是‘(’结束符，则将运算符栈中的栈顶元素退出来，继续读表达式中的下一个符号，重复步骤（3）和（4）；

    [4]若读到的运算符的优先级等于或小于之前的运算符的优先级，则从操作数中退出2个，从运算符中退出一个进行运算，将运算结果存入操作数栈；再把之前读到的运算符与目前的运算符栈顶比较，重复步骤（4）（即现在不读下一个元素）；

所以，我们只要按照这个虚伪的规则去做就没有问题！

很好，这就是这个程序的原型；

接下是虚伪的某转换函数：

然后是乘除号：

最后是吃数字

弹出数字+符号

接下来的事情就是码代码了；

#include<cstdio>
#include<cstdlib>
#include<cmath>
const int max_size=200;

struct op_stack
{
	char data[max_size];
	int top;
}op;

struct st_stack
{
	int data[max_size];
	int top;
}st;

void trans(char exp[],char postexp[]);
int compvalue(char postexp[]);

int main(void)
{
	char exp[max_size]={};
	scanf("%s",exp);

	char postexp[max_size]={};
	
	trans(exp,postexp);

	int ans=compvalue(postexp);
	printf("%d\n",ans);
	return 0;
}

void trans(char exp[],char postexp[])
{
	char ch;
	int i=0,j=0;
	
	op.top=-1;
	ch=exp[i];
	i++;
	
	while (ch!='\0')
	{
		switch(ch)
		{
			case '(':
				op.top++;
				op.data[op.top]=ch;
				break;
			case ')':
				while(op.data[op.top]!='(')
				{
					postexp[j]=op.data[op.top]; j++;
					op.top--;
				}
				op.top--;
				break;
			case '+':
			case '-':
				while (op.top!=-1 && op.data[op.top]!='(')
				{
					postexp[j]=op.data[op.top];
					j++;
					op.top--;
				}
				op.top++; op.data[op.top]=ch;
				break;
			case '*':
			case '/':
			case '^':
				while(op.top!=-1 && op.data[op.top]!='('&&(op.data[op.top]=='*'||op.data[op.top]=='/'||op.data[op.top]=='^'))
				{
					postexp[j]=op.data[op.top];
					j++;
					op.top--;
				}
				op.top++;
				op.data[op.top]=ch;
				break;
			case ' ':
				break;
			default:
				while (ch>='0'&&ch<='9')
				{
					postexp[j]=ch;
					j++;
					ch=exp[i];
					i++;
				}
				i--;
				postexp[j]='#'; j++;
		}
		ch=exp[i];
		i++;
	}

	while(op.top!=-1)
	{
		postexp[j]=op.data[op.top];
		j++;
		op.top--;
	}
	postexp[j]='\0';
	return;
}

int compvalue(char postexp[])
{
	int d=0.0;
	
	int i=0;
	st.top=-1;
	
	char ch=postexp[i++];

	while (ch!='\0')
	{
		switch(ch)
		{
			case '+': 
				st.data[st.top-1]=st.data[st.top-1]+st.data[st.top];
				st.top--; 
				break;
			case '-': 
				st.data[st.top-1]=st.data[st.top-1]-st.data[st.top];
				st.top--; 
				break;
			case '*': 
				st.data[st.top-1]=st.data[st.top-1]*st.data[st.top];
				st.top--; 
				break;
			case '^':
				st.data[st.top-1]=pow(st.data[st.top-1],st.data[st.top]);
				st.top--; 
				break;
			case '/':
				if(st.data[st.top]!=0)
				st.data[st.top-1]=st.data[st.top-1]/st.data[st.top];
				else
				{
					printf("Error\n");
					exit(0);
				}
				st.top--;
				break;
			default:
				d=0;
				while(ch>='0'&&ch<='9')
				{
					d=10*d+ch-'0';
					ch=postexp[i];
					i++;
				}
				st.top++;
				st.data[st.top]=d;
		}
		ch=postexp[i++];
	}
	return st.data[st.top];
}