前言
今天在刷hash的题目，突然做到了noip2005提高组的等价表达式的题目。我的思路是写一个未知数的取值数组x[]，然后各个代入原式求值保存。再对于选项中的各个表达式进行相应的代入，且比对，如果全部相符，就可以认为是等价表达式。
不过另一个很严肃的问题是，我好像忘了怎么进行中缀表达式求值了……
这天，蒟蒻们又回想起了曾经学栈时被中缀式求值所笼罩的阴影
所以我就打算这个再总结一下。
方法
转后缀表达式
对于数字：直接输入target数组。
由于target数组为char类型，所以这里的数字我没有直接求出，还是一个一个拆开输入target，但为了便于第二步求值，所以输入一串数字之后，再加一个空格隔开。
对于符号：
①对于(，由于优先级最高，直接压栈；
②对于)，直接在栈中开始弹出，直到碰到(为止，且(只弹出不输入target；
③对于其他符号，在压栈之前先弹出栈中所有比其优先级更高的符号，再压栈。
结束
原数组扫描完成后，将栈中剩余的所有元素依次弹出。
后缀表达式求值
对于数字：压栈；
对于符号：取出栈中的顶上两个元素，进行相应操作，再将结果压入栈中。
注意
①如果表达式的括号不匹配，运算会出现问题。（你可能需要在input()函数中再匹配一下括号什么的？）
②负数有点不好处理，所以我就再输入上面做了点手脚，在所有代表负号的符号前加了0。
③建议将value()函数中的乘号的优先级设计的比除号的优先级更高，这样有利于避免整数除法所带来不必要的误差。
④代码中的value()函数用来保存各个符号的优先级，这里只支持加减乘除，乘方及括号。不过支持再添加其他操作符哦~
实现
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;
const int size=1010;
char str[size],target[size];
inline int value(char c)
{
switch(c)
{
case '+':return 1;
case '-':return 1;
case '*':return 3;
case '/':return 2;
case '^':return 4;
case '(':return 0;//避免被其他符号弹出
}
}
void input(char t[])
{
int p=0;
char ch=getchar();
while(ch!='\n')
{
if(ch=='-'&&(p==0||t[p-1]=='('))//处理负号
{
t[p++]='0';
}
t[p++]=ch;
ch=getchar();
}
}
void change(char s[],char t[])
{
int i=0,p=0,top=0,len=strlen(s),val;
char *stack=new char[size];
while(i<len)
{
if(s[i]>='0'&&s[i]<='9')
{
while(s[i]>='0'&&s[i]<='9')
t[p++]=s[i++];
t[p++]=' ';
}
else
{
if(s[i]==')')
{
while(top>0&&stack[top]!='(')
t[p++]=stack[top--];
top--;
i++;
continue;
}
if(s[i]=='(')//对它的优先级进行了处理，所以需要强制压栈
{
stack[++top]=s[i++];
continue;
}
val=value(s[i]);
while(top>0&&val<=value(stack[top]))
t[p++]=stack[top--];
stack[++top]=s[i++];
}
}
while(top>0)
t[p++]=stack[top--];
}
int calc(char t[])
{
int i=0,top=0,len=strlen(t),a,b,res,ans;
int *stack=new int[size];
while(i<len)
{
if(t[i]==' ')
i++;
else if(t[i]>='0'&&t[i]<='9')
{
res=0;
while(t[i]>='0'&&t[i]<='9')
res=res*10+t[i++]-'0';
stack[++top]=res;
}
else
{
b=stack[top--];
a=stack[top--];
switch(t[i])
{
case '+':stack[++top]=a+b;break;
case '-':stack[++top]=a-b;break;
case '*':stack[++top]=a*b;break;
case '/':stack[++top]=a/b;break;
case '^':stack[++top]=pow(a,b);break;
}
i++;
}
}
return stack[top--];
}
int main()
{
freopen("in.txt","r",stdin);
input(str);
change(str,target);
printf("%d\n",calc(target));
return 0;
}