# 用栈求表达式的题目,我只做了将中缀表达式转化成后缀表达式的函数convert,但是convert出了些问题。比如输入6+5*3时,它输出的就是653*+,但是输入6*5+3时他只会输出65*3,最后的+被吃掉了,变成了倆空格,调试的时候这个空格出来的也很诡异,求帮助!****
/*
读取到操作数的时候,如果比栈顶操作符的优先级高,或者是左括号,则直接入操作符栈;
反之,如果比栈顶优先级低,或者右括号,则出操作符栈,进逆波兰式栈,或是知道读取到左括号时停止,然后将当前操作符插入。
*/
#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>
#include <math.h>
typedef struct node {
int data;
struct node * next;
}node,*pnode;
typedef struct stack {
pnode top;
pnode bottom;
}stack,*pstack;
pstack initstack (void);
void push(pstack s,int i);
int gettop(pstack s);
void pop(pstack s,int &i);
bool IsEmpty(pstack s);
void traverse_stack(pstack s);
void convert(pstack polish,pstack oper);
bool IsOperator(int in);
int privilege(int i);
bool IsSpace(int in) ;
void plus(pstack polish,pstack oper);
int main(void) {
pstack polish,oper;
polish = initstack();//polish是逆波兰式
oper = initstack();//oper是操作符栈
convert(polish,oper);
traverse_stack(polish);
traverse_stack(oper);
return 0;
}
void convert(pstack polish,pstack oper) {//将中缀表达式转换成逆波兰式
int in = 0;
int m = 0;
printf("\n***************WARNING!PAY ATTENTION TO THE FORMAT OF ','***************\n");
in = getchar();
while((in!=',')&&(in!='\n')) {//如果读取到空格则直接读取下一个字符
if(IsSpace(in)) {
in = getchar();
continue;
}
if(!IsOperator(in)) {//读取的值是数值是直接进入polish栈
push(polish,in);
}else {
if((in == '(')||(privilege(in) > privilege(gettop(oper)))) {//*******如果比栈顶操作符的优先级高,或者是左括号,则直接入操作符栈
push(oper,in);
}else {//****************否则
while(1){//********如果当前操作符是右括号,则将oper出栈,直到将栈内的左括号弹出 ;如果是操作符,则将oper全部出栈至polish//这个while循环在调试的时候,步骤跳的有异常。
printf("\ntest");
if((m=='(')||(m=='#')||(IsEmpty(oper))) {
break;//*********读取到左括号或oper已经空时退出循环
}
pop(oper,m);
push(polish,m);
}//while
}
}//if
in = getchar();
}//最外层while
if(!IsEmpty(oper)) {//将oper中剩余的操作符压入polish栈中
plus(polish,oper);
}
return;
}
int privilege(int in) {
switch (in) {
case '-':
return 1;
case '+':
return 1;
case '*':
return 2;
case '/':
return 2;
case '%':
return 2;
case '^':
return 3;
default:
return 0;
}
}
void plus(pstack polish,pstack oper) {
int in;
in = gettop(oper);
while(in!='#') {
push(polish,in);
pop(oper,in);
in = gettop(oper);
}
}
bool IsOperator(int in) {
int operate[8] = {'+','-','*','/','%','^','(',')'};
int i;
for(i = 0;i <= 7;i++) {
if (in == operate[i]) {
return true;
}
}
return false;
}
bool IsSpace(int in) {
return in==' '||in == '\t';
}
pstack initstack (void){
stack *s;
s = (stack*)malloc(sizeof(stack));
s->top = (node*)malloc(sizeof(node));
s->bottom = s->top;
s->bottom->data = '#';
return s;
}
void push(pstack s,int i) {
pnode new_node = (node*)malloc(sizeof(node));
if(!new_node){
printf("\nfailure to allocate memory!");
return;
}
new_node->data = i;
new_node->next = s->top;
s->top = new_node;
return;
}
int gettop(pstack s) {
return s->top->data;
}
void pop(pstack s,int &i) {
pnode dele_node;
if(IsEmpty(s)) {
printf("\nthe stack is empty!(from:pop)");
return;
}
dele_node = s->top;
i = dele_node->data;
//printf("\nthe value is %c",ch);
s->top = s->top->next;
free(dele_node);
dele_node = NULL;
return;
}
bool IsEmpty(pstack s) {
return s->top == s->bottom ? true : false;
}
void traverse_stack(pstack s) {
if(IsEmpty(s)) {
printf("\nthe stack is empty!(from:traverse)");
return;
}
pnode p;
int i = 0;
p = s->top;
while(p!=s->bottom) {
printf("\nthe %dth element is %c",++i,p->data);
p = p->next;
}
return;
}