栈实现四则运算

    休息一会儿。

来恒为的第三天了，到目前为止做的事情就是把四则运算的栈实现完成的差不多了，说差不多是因为对输入会出错的判断和输出还没有实现。

来说说这个程序吧。

首先，对输入的表达式是以字符为单位读入的，对每个读入的字符进行判断，数字放到character栈中，算符放到operator栈中，另外定义了push和pop的函数进行进栈和出栈的操作，（大二学数据结构的时候对各种结构一直没有清晰的认识，现在觉得结构的特性取决于对结构的操作，也就是他的行为决定了他的特性，然后才有栈，队列等名字）。初始化的时候先将‘#’字符压到operator栈中，此时其优先级是最低的，方便对以后读入的算符进行比较和处理。优先级的判断是通过定义了两个数组实现的。当后来读入的算符的优先级低于已经在operator中栈顶的算符时就弹出operator中的算符以及character中的两个数字用operate函数进行运算，运算的数值push到character栈中，继续进行算符的判断看是否需要继续进行运算。表达式必须是以‘#’结尾的，当operator中的栈顶和最后读入的字符都是‘#’时就结束循环，返回character中栈顶元素，这就是最后的结果。

整体的思路就是对输入表达式的依次读入和处理，对一开始就出现的‘+’和‘-’要进行特殊的处理，设置一个标志位对负数进行标记，正数直接覆盖。由于是一位一位读取的，对多位数的处理要用求和的方式。难点是对运算符优先级的判断，特别是括号的处理，这也是我觉得最为巧妙的地方。设置两个整型数组，分别对应栈内和栈外的算符优先级。对括号的处理上，栈外的‘）’应该与栈内的‘(’优先级相同，把两者之间的运算解决之后要将栈内的‘(’pop出来，以免影响后续的操作。

清单：mystack栈，in[7],out[7]优先级数组，ch[7]保存算符对应的数字。函数：push，pop，gettop，initstack，compare，evaluate

对输入格式的错误处理还没有具体实现。

做事一定要狠抓效率，在最短的时间内实现最核心的功能。我很没耐心，拖久了就不想去做了。所以效率是这几个月的重中之重！

先这样。
附上代码
#include <stdio.h>
#include <ctype.h>  //header file of isdigit
#define MAXSIZE 100//the max length of the expresion
char ch[7] = {'+','-','*','/','(',')','#'};
int in[7] = {3,3,5,5,1,6,0};//the order of operator in the stack
int out[7] = {2,2,4,4,6,1,0};//the order of operator out the stack
struct mystack
{
int stack[MAXSIZE];
int top;
};
typedef struct mystack mystack;
void Initstack(mystack *s)//initial the stack
{
s->top = 0;
}
void Push(mystack *s,int x)//to push a number into a stack
{
s->top++;
s->stack[s->top] = x;
}
void Pop(mystack *s,int *x)//to pop a number out of a stack
{
*x = s->stack[s->top];
s->top--;
}
int Gettop(mystack s)//to get the top number of a stack
{
return s.stack[s.top];
}
int Trans(char c)//to translate the operator to a number in order
{
switch(c)
{
case '+':return 0;break;
case '-':return 1;break;
case '*':return 2;break;
case '/':return 3;break;
case '(':return 4;break;
case ')':return 5;break;
default :return 6;break;
}
}
char Compare(char c1,char c2)//compare the order of the operator according to the array given at the front and return a char
{
int i1 = Trans(c1);
int i2 = Trans(c2);
if(in[i1] < out[i2])
return '<';
else if(in[i1] > out[i2])
return '>';
else
return '=';
}
int Operate(int a,int op,int b)//do the calculate according to the number in the array
{
switch (op)
{
case 0:return a+b;break;
case 1:return a-b;break;
case 2:return a*b;break;
default:return a/b;break;
}
}
int Evaluate()//deal with the expression inputed char by char
{
char c;
int sum,op,a,b,x;
int j = 1,k = 1;
mystack operator,character;//operator for the operator stack,character for the number stack
Initstack(&operator);
Push(&operator,Trans('#'));
Initstack(&character);

c = getchar();
if (c == '+')
c = getchar();//ignore the '+' in front of the expression
else if (c == '-')
{
c = getchar();//ignore the '-' in front of the expresion
j = 0;//mark the negative number
}
while(c != '#'|| ch[Gettop(operator)] != '#')//the condition of the cycle
{
if(isdigit(c))//include in the ctype.h to judge whether it is a number
{
sum = 0;
while(isdigit(c))
{
if(j)
sum = sum * 10 + (c - '0');
else
sum = sum * 10 - (c - '0');
c = getchar();
}
Push(&character,sum);//push the inputed number into the character stack
j = 1;//back the mark
}
else
{
switch(Compare(ch[Gettop(operator)],c))
{
case '>'://do the calculte if the operator in the stack is bigger than the operator out of the stack
Pop(&operator,&op);
Pop(&character,&b);//notice the pop order
Pop(&character,&a);
Push(&character,Operate(a,op,b));
// c = getchar();//no need to getchar
break;
case '<':
Push(&operator,Trans(c));
c = getchar();
break;
case '='://very important //about '(' and ')'
Pop(&operator,&x);//pop the '(' in the stack
c = getchar();
break;
}
}
}
return Gettop(character);//the result of the expression
}
int main()
{ int result;
  printf("Input the expression:\n");
result = Evaluate();
printf("The result is :%d\n",result);

}