Stack-逆波兰式

假设表达式由单字母变量和双目四则运算构成。试写一个算法，将一个通常书写形式且书写正确的表达式转为逆波兰式。 【分析】算法的思想：所有的变量在逆波兰式中出现的先后顺序和在原表达式中出现的相同，因此只需要设立一个\"栈\"，根据操作符的\"优先级\"调整它们在逆波兰式中出现的顺序。 #include #include #define STACK_INIT_SIZE 100 #define STACK_INCREAMENT 10 typedef struct { //栈

char *base; char *top;

int stackSize; } Stack;

void initStack(Stack &stack) { //初始化栈

stack.base = stack.top = (char *)malloc(sizeof(char) * STACK_INIT_SIZE); stack.stackSize = STACK_INIT_SIZE; }

void push(Stack &S, char p) { //入栈

if(S.top - S.base >= S.stackSize) {

S.base=(char*)realloc(S.base,(S.stackSize+STACK_INCREAMENT)*sizeof(char)); S.top = S.stackSize + S.base; S.stackSize += STACK_INCREAMENT; }

*S.top++ = p;

}

void pop(Stack &stack, char &p) { //出栈

if(stack.base == stack.top) { p = NULL; return ; }

p = *--stack.top; }

char getTop(Stack stack) { //获得栈顶元素 if(stack.base == stack.top) return NULL; return *(stack.top - 1); }

bool isAlpha(char p) { //判断是不是字母 }

return (p >= 'a' && p <= 'z') || (p >= 'A' && p <= 'Z') ? true : false;

int precede(char a, char b) {

switch (a) {

case '/' :

case '*' : return 1; break; case '+' :

case '-' :

switch(b) { case '/' : case '*' : return -1; break; default : return 1; } break;

default : switch(b) {

}

case '#' : return 0; break; default : return -1;

} }

void NiBoLan(char *str, char *newStr) { //转换成逆波兰式

Stack stack; initStack(stack); char *p, *q, c;

p = str; q = newStr; push(stack, '#'); while(*p) { }

if(isAlpha(*p)) *q++ = *p; else { c = getTop(stack); if(precede(*p, c) > 0) push(stack, *p); }

else { while(precede(getTop(stack), *p) >= 0 && *p) { }

pop(stack, c); *q++ = c; }

push(stack, *p);

p ++;

}

void main() { }

char str[100]; char newStr[100]; int i;

for(i=0; i<100; i++) str[i] = newStr[i] = '\\0'; printf(\"请输入表达式：\\n\"); scanf(\"%s\NiBoLan(str, newStr);

printf(\"其对应的逆波兰式为：%s\\n\