主题:表达式求值,可以解决一切带负数的正确合理的表达式
#include<iostream>
using namespace std;
typedef struct SqStack{
int * base;
int * top;
int size;
}SqStack;
#define STACK_INIT_SIZE 100
#define STACKINCREMENT 20
void InitSqStack(SqStack &t);
void push(SqStack &t, int n);
int out(SqStack &t);
int Empty( SqStack &t);
char GetTop(SqStack &t);
char Precede(char ,char);
int main(){
char ch;
SqStack OPTR;InitSqStack(OPTR);
SqStack OPND;InitSqStack(OPND);
push(OPTR,'=');
ch=getchar();
if(ch=='-'){ //第一个数为负数
int m=0;
ch=getchar();
while(ch<='9'&&ch>='0'){
m=m*10+ch-48;
ch=getchar();
}
push(OPND,m*(-1));
}
while(ch!=10){
int m=0; int flag=1; char ch1=ch;
if(ch1=='('){
char ch2;
push(OPTR,ch);
while((ch=getchar())=='(')
push(OPTR,ch);
ch2=ch;
if(ch2=='-'){ //出现负数
flag=-1;
ch=getchar();
while(ch<='9'&&ch>='0'){
m=m*10+ch-48;
ch=getchar();
}
}
else
{
while(ch<='9'&&ch>='0'){
m=m*10+ch-48;
ch=getchar();
}
}
if(ch==')') //形如(-1)的负数 还有形如(-1+2*5 中的负数
{
out(OPTR);
ch=getchar();
}
}
else {
while(ch<='9'&&ch>='0'){
m=m*10+ch-48;
ch=getchar();
}
}
if(m)
push(OPND,m*flag);
switch(Precede(GetTop(OPTR),ch)){
case '<':push(OPTR,ch);ch=getchar();break;
case '=':out(OPTR);ch=getchar();break;
case '>':{
int m2=out(OPND),m1=out(OPND); //注意m1和m2的顺序 后一个操作数先出来用m2接收
switch(out(OPTR))
{
case '+':push(OPND,m1+m2);break;
case '-':push(OPND,m1-m2);break;
case '*':push(OPND,m1*m2);break;
case '/':push(OPND,m1/m2);break;
}
break;
}
}
}
printf("%d",out(OPND));
getchar();
}
void push(SqStack &t, int n){
if((t.top-t.base)>=t.size){
t.base=(int *)realloc(t.base,(t.size+STACKINCREMENT)*sizeof(int));
if(!t.base)
exit(1);
}
*(t.top)=n;
t.top++;
}
int out(SqStack &t){
t.top--;
return *(t.top);
}
int Empty( SqStack &t){
int m=(t.top-t.base);
return m;
}
char GetTop(SqStack &t){
return *(t.top-1);
}
char Precede(char c,char d)
{
char youxian[7][7]=
{
{'>','>','<','<','<','>','>'},
{'>','>','<','<','<','>','>'},
{'>','>','>','>','<','>','>'},
{'>','>','>','>','<','>','>'},
{'<','<','<','<','<','=','>'},
{'>','>','>','>','>','>','>'},
{'<','<','<','<','<','>','='}
};
char opt[7]={'+','-','*','/','(',')','='};
int m,n,i;
for(i=0;i<7;i++)
{
if(c==opt[i])
{
m=i;
}
if(d==opt[i])
{
n=i;
}
}
return youxian[m][n];
}
void InitSqStack(SqStack &t){
t.base=(int *)(malloc(sizeof(int)*STACK_INIT_SIZE));
if(!t.base)
exit(1);
t.top=t.base;
t.size=STACK_INIT_SIZE;
}