获取后缀表达式的原理是用一个字符数组来存放后缀表达式，
用一个栈来暂时存放运算符，入栈出栈和字符数组的存储规则为：
一.当字符是操作数，直接存入字符数组中
二.当字符不是操作数，分三种情况讨论
1.字符是‘（’:当前字符直接入栈
2.字符是‘）’：一直出栈，将出栈的字符存入字符数组中，直到栈顶元素是‘（’时，将栈顶元素出栈，跳出循环，当前字符不入栈。
3.字符是运算符：当字符的优先级比栈顶的优先级小或相等时，一直出栈，将出栈的运算符存入字符数组，直到字符的优先级比栈顶的运算符优先级大，或者栈为空的时候，停止循环，当前字符入栈。
栈结构的编写：
stack.h
#include"stdlib.h"
typedef int bool;
#define true 1;
#define false 0;
typedef struct datanode{
char value;
struct datanode* next;
}datanode;
typedef struct _stack{
datanode* top;//指向栈顶（链表头）
datanode* base;//指向栈底（链表尾）
}*stack, _stack;
stack init();
datanode* createnode(char value);
void push(stack stackobj, char value);
char pop(stack stackobj);
bool isempty(stack stackobj);
stack.c
#include"stdlib.h"
#include"stack.h"
stack init()
{
stack tmpstack = (stack)malloc(sizeof(_stack));
if (tmpstack == NULL){ return NULL; }
tmpstack->base = NULL;
tmpstack->top = NULL;
return tmpstack;
}
datanode* createnode(char value)
{
datanode* tmp = (datanode*)malloc(sizeof(datanode));
if (tmp == NULL){ return NULL; }
tmp->value = value;
tmp->next = NULL;
return tmp;
}
void push(stack stackobj, char value)
{
if (stackobj == NULL){ return; }
datanode* tmp = createnode(value);
if (tmp == NULL){ return; }
tmp->next = stackobj->top;
stackobj->top = tmp;
if (tmp->next == NULL)
{
stackobj->base = tmp;//其实这个base没什么卵用,只是标准的栈结构有base,就给他做一个
}
}
char pop(stack stackobj)
{
if (stackobj == NULL){ return; }
if (stackobj->top == NULL)//栈为空
{
return NULL;
}
datanode* tmp = stackobj->top;
stackobj->top = stackobj->top->next;
return tmp->value;
}
bool isempty(stack stackobj)
{
if (stackobj == NULL){ return; }
if (stackobj->top == NULL)
{
return true;
}
return false;
}
maintest.c
#include"stdlib.h"
#include"stack.h"
typedef int bool;
#define true 1;
#define false 0;
void pushinbuffer(char* buffer, char value);
//获取后缀表达式
void getbackcom2()
{
stack mystack = init();
char buffer1[100] = “”;//用来存放表达式
printf(“请输入表达式：”);
scanf("%s", buffer1);
printf("%s\n", buffer1);
char buffer2[100] = “”;
char* p = buffer1;
while (*p)
{
if (*p >= ‘0’&&*p <= ‘9’)
{
pushinbuffer(buffer2, *p);
}
else
{
char tmp1;
if (*p == ‘)’)
{
while (1)
{
if (mystack->top->value == ‘(’)
{
pop(mystack);
break;
}
tmp1 = pop(mystack);
pushinbuffer(buffer2, tmp1);
}
}
else if (*p == ‘(’)
{
push(mystack,*p);
}
else
{
while (mystack->top != NULL&&mystack->top->value!=’(’&&compare(*p, mystack->top->value))
{
tmp1 = pop(mystack);
pushinbuffer(buffer2, tmp1);
}
push(mystack, p);
}
}
p++;
}
while (mystack->top != NULL)
{
char tmp2 = pop(mystack);
pushinbuffer(buffer2, tmp2);
}
printf("%s\n",buffer2);
}
void pushinbuffer(char buffer, char value)
{
if (buffer == NULL || value == NULL)
{
return;
}
int len;
len = strlen(buffer);
buffer[len] = value;
buffer[len + 1] = 0;
}
bool compare(char new,char top)
{
int newp = getpriority(new);
int topp = getpriority(top);
if (newp <= topp)
return true;
return false;
}
int getpriority(char c)
{
int x;
switch ©
{
case ‘+’:
case ‘-’:
x = 1; break;
case ‘*’:
case ‘/’:
x = 2; break;
}
return x;
}
void main()
{
getbackcom2();
system(“pause”);
}
经验与总结：1.编写时逻辑一定要先想清楚，不然全是bug。
2.如何在字符串后面添加字符：
char buffer[100]="";
len = strlen(buffer);
buffer[len] = value;
buffer[len + 1] = 0;