Stack application
上篇博文里用数组实现stack，然后做了个简单的小括号匹配应用。这次我用stack去实现表达式的infix to postix的转换。如2+3+4*5变为2 3+ 4 5* +.来实现表达式的stack方式求值。只应对了简单的加减乘除，而且输入是连续的，当然后面我可以改进。不过看起来时间不够，先把架子搞出来。收获：
1. 变量声明要放在主函数内的前面。因为我用的是visual C++6.0 ，而且用的是C语言，根据K&R标准，是要放在前面的，不过ANSI C等可以随时用随时定义。
2. 还是那句话，眼过千遍不如手过一遍（CU的一个大佬说的^^).光说不练还是不会，一写代码各种syntax error，太丢人。
3. 实现过程中主要注意两点，一是操作符的优先级，而是操作符的结合顺序。
待整理：
1. 包含括号的情形。小括号具有最高的优先级，碰到比括号是将最近匹配的括号内全部输出。
2. 输入有空白的情形。
//stack appliation ---expression convertion from infix to postfix
#include <stdio.h>
#include <stdlib.h> //include exit(),malloc() function。
#include <string.h> //include strlen function
#include <ctype.h>
#define EMTPTYSTACK -1 //define the empty stack arry subcript, so the element would be started from array
#define MAXELEMENTS 100
struct StackRecord;
typedef struct StackRecord *Stack;
typedef char ElementType ; //define element type
void Error (char input[])
{
printf("%s\n",input);
exit(4);
}
struct StackRecord
{
int Capacity; // record the total space allocated for this stack
int TopOfStack; //record the Array subscript of top element
ElementType *Array; //record the allocated array address
};
int IsEmpty(Stack S);
int IsFull(Stack S);
void Push(ElementType x, Stack S);
void Pop(Stack S);
Stack CreateStack(int Maxelement);
void MakeEmpty (Stack S);
ElementType Top(Stack S);
ElementType PopAndTop(Stack S);
int IsEmpty (Stack S)
{
return S->TopOfStack == EMTPTYSTACK;
}
int IsFull (Stack S)
{
return S->TopOfStack == S->Capacity-1; //topofstack is ranged from 0 to MAXELEMENTS-1
}
void Push(ElementType x, Stack S)
{
if(IsFull(S))
Error("Out of Space !!!\n");
else
S->Array[ ++S->TopOfStack ] = x;
}
void Pop (Stack S)
{
if ( IsEmpty( S) )
Error("Empty Stack !!\n");
else
S->TopOfStack--;
}
Stack CreateStack (int Maxelement)
{
Stack S;
S = malloc(sizeof(struct StackRecord));
if (S == NULL)
Error("Out of Space !!!\n");
S->Array=malloc(sizeof(ElementType)*Maxelement);
if (S->Array == NULL)
Error("Out of Space !!!\n");
S->Capacity = Maxelement;
MakeEmpty (S);
return S;
}
void MakeEmpty (Stack S)
{
S->TopOfStack = EMTPTYSTACK;
}
ElementType Top(Stack S)
{
return S->Array;
}
ElementType PopAndTop(Stack S)
{
return S->Array; //operator precedence of -> (left to right) is higher than --/++ ;
}
int Getprecedence(char x)
{
if (x == '+' || x == '-')
return 1;
if (x == '*' || x == '/' )
return 2;
if (x == '(' || x == ')')
return 3;
return -1;
}
int ZeroIfNegative (int x)
{
if (x<0)
return 0;
else
return x;
}
int main (void)
{
char ch;
int stack_precedence;
int input_precedence;
Stack stack_instance;
stack_instance=CreateStack(MAXELEMENTS);
while( (ch=getchar()) != EOF && ch != 'q')
{
if( isdigit(ch) )
putchar(ch);
else
{
if ( IsEmpty(stack_instance) ) //push operator for empty stacks
Push(ch,stack_instance);
else
//{
//if ( Getprecedence (Top(stack_instance)) < Getprecedence(ch) )
//Push(ch, stack_instance);
//else
{ while( (Getprecedence (Top(stack_instance)) >= Getprecedence(ch) ) && (!IsEmpty(stack_instance)) )
//because addition/subtraction/multiplication/division are all associated from left to right,so it is >=,
//otherwise it will be > only.
{printf("%c",Top(stack_instance) );
Pop(stack_instance);
}
Push(ch,stack_instance);
}
putchar(' ') ;//to split the digits
}
}
while(! IsEmpty(stack_instance) )
{putchar(Top(stack_instance) );
Pop(stack_instance);
}
return 0;
}
页:
[1]