字首表達式轉字尾表達式及求值經典代碼

#define _CRT_SECURE_NO_WARNINGS

#include<stdio.h>

#include<stdlib.h>

typedef struct stack

{

int top;

char s[100];

}Stack;

typedef struct OPstack

{

int top;

float s[100];

}OPStack;

void InitStack(Stack *stack)

{

stack->top = 0;

}

void pushStack(Stack *stack,char ch)

{

stack->s[stack->top++] = ch;

}

_Bool isEmpty( Stack *stack)

{

if (stack->top == 0)

{

return 1;

}

return 0;

}

_Bool getTop( Stack *stack, char *ch)

{

*ch = (stack->s)[stack->top - 1];

return 1;

}

char Popstack(Stack *stack)

{

stack->top = stack->top-1;

return stack->s[stack->top];

}

void ZhongToHou(char * source, char *exp)

{

Stack stack;

InitStack(&stack);

int i = 0;

int j = 0;

char ch = source[i++];

char e = 0;

while (ch != '\0')

{

switch (ch)

{

case '(':

pushStack(&stack,ch);

break;

case ')':

while (!isEmpty(&stack) && getTop(&stack,&e) && e !='(')

{ 

//ch=Popstack(&stack);

//printf("你好=%c\n", ch);

exp[j++] = Popstack(&stack);

}

Popstack(&stack);//彈出'('

break;

case '+':

case '-':

while (!isEmpty(&stack) && getTop(&stack, &e) && e != '(')

{

exp[j++] = Popstack(&stack);

}

pushStack(&stack, ch);

break;

case '*':

case '/':

while (!isEmpty(&stack) && getTop(&stack, &e) && e == '*'||e=='/')

{

exp[j++] = Popstack(&stack);

}

pushStack(&stack, ch);

break;

default:

while(ch >= '0' && ch <= '9')

{

exp[j++] = ch;

ch = source[i++];

}

i--;

exp[j++] = ' ';

break;

}

ch = source[i++];

}

while (!isEmpty(&stack))

{

exp[j++] = Popstack(&stack);

}

exp[j] = '\0';

}

float ComputeExpress(char a[])     //計算字尾表達式的值

{

OPStack s;

s.top = -1;

int i = 0,result;

int j = 0;

float x1, x2;

char ch = a[i];

while (ch!='\0')

{

if (ch >= '0' && ch <= '9')

{

int v = 0;

while (ch>='0' && ch <='9')

{

v = v*10 + (ch - '0');

i++;

ch = a[i];

}

i--;

s.top++;

s.s[s.top] = v;

//printf("\nnum=%d\n", v);

}

else

{

switch (ch)

{

case '+':

x1 = s.s[s.top];

s.top--;

x2 = s.s[s.top];

s.top--;

result = x1 + x2;

s.top++;

s.s[s.top] = result;

printf("result===%d,top=====%d", result, s.top);

break;

case '-':

x1 = s.s[s.top];

s.top--;

x2 = s.s[s.top];

s.top--;

result = x2-x1;

s.top++;

s.s[s.top] = result;

break;

case '*':

x1 = s.s[s.top];

s.top--;

x2 = s.s[s.top];

s.top--;

result = x2 * x1;

s.top++;

s.s[s.top] = result;

break;

case '/':

x1 = s.s[s.top];

s.top--;

x2 = s.s[s.top];

s.top--;

result = x2 / x1;

s.top++;

s.s[s.top] = result;

break;

default:

break;

}

}

i++;

ch = a[i];

}

if (s.top != -1)       //如果棧不為空，将結果出棧并傳回

{

result = s.s[s.top];

s.top--;

if (s.top == -1) {

printf("result===%d", result);

return result;

}

else

{

printf("表達式錯誤!\n");

exit(-1);

}

}

}

void main()

{

printf("請輸入表達式:");

char a[100] = { 0 }; char  b[100] = { 0 };

scanf("%s", a);

printf("中綴表達式:");

printf("%s", a);

ZhongToHou(a,b);

printf("字尾表達式:");

printf("%s",b);

printf("結果為:");

printf("結果= %lf", ComputeExpress(b));

system("pause");

}