#include <stdio.h>
#include <stdlib.h>
#include <
malloc.h>
#define STACK_INIT_SIZE 100
#define STACK_INCREAMENT 10
#pragma warning(disable:4996)
//我用的vs2015，不加这句用scanf会报错（使用了unsafe的函数）
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);
}
char *NIBOLAN(
char *e)
/* 返回表达式e的逆波兰式 */
{//栈s1用于存放运算符，栈s2用于存放逆波兰式
Stack s1, s2;initStack(s1);initStack(s2);
push(s1, '#');
//假设字符'#'是运算级别最低的运算符，并压入栈s1中
//p指针用于遍历传入的字符串，ch用于临时存放字符,length用于计算字符串长度
char *p = e, ch;
int length =
0;
for (; *p !=
'\0'; p++)
//逐个字符访问
{
switch (*
p)
{
//遇'('则直接入栈s1
//遇')'则将距离栈s1栈顶的最近的'('之间的运算符，逐个出栈，依次送入栈s2,此时抛弃'('
case '(':push(s1, *p);
break;
case ')':
while (getTop(s1) !=
'(')
{
pop(s1, ch);
push(s2, ch);
}pop(s1, ch); break;
//遇下列运算符，则分情况讨论：
//1.若当前栈s1的栈顶元素是'('，则当前运算符直接压入栈s1；
//2.否则，将当前运算符与栈s1的栈顶元素比较，若优先级较栈顶元素大，则直接压入栈s1中,
// 否则将s1栈顶元素弹出，并压入栈s2中，直到栈顶运算符的优先级别低于当前运算符，然后再将当前运算符压入栈s1中
case '+':
case '-':
for (ch = getTop(s1); ch !=
'#'; ch =
getTop(s1))
{
if (ch ==
'(')
break;
else pop(s1, ch); push(s2, ch);
}push(s1, *p); length++;
break;
case '*':
case '/':
for (ch = getTop(s1); ch !=
'#'&&ch !=
'+'&&ch !=
'-'; ch =
getTop(s1))
{
if (ch ==
'(')
break;
else pop(s1, ch); push(s2, ch);
}push(s1, *p); length++;
break;
default:
push(s2, *p); length++
;
}
}
//若栈s1非空，则将栈中元素依次弹出并压入栈s2中
while (s1.
base!=s1.top && getTop(s1) !=
'#')
{
pop(s1, ch);
push(s2, ch);
}
//最后将栈s2输出，逆序排列成字符串;
char *
result;
result = (
char *)
malloc(
sizeof(
char)*(length +
1));
result +=
length;
* result =
'\0';
result--
;
for (; s2.
base!=s2.top; result--
)
{
pop(s2, ch);
* result =
ch;
}
++
result;
return result;
}
void main()
{
while (
1)
{
char str[
100];
int i;
for (i =
0; i<
100; i++)str[i]=
'\0';
printf("请输入表达式：\n");
scanf("%s",str);
printf("%s", NIBOLAN(str));
}
}
(1)首先，需要分配2个栈，栈s1用于临时存储运算符（含一个结束符号），此运算符在栈内遵循越往栈顶优先级越高的原则；栈s2用于输入逆波兰式，为方便起见，栈s1需先放入一个优先级最低的运算符，在这里假定为'#'；
(2)从中缀式的左端开始逐个读取字符x，逐序进行如下步骤：
1.若x是操作数，则分析出完整的运算数（在这里为方便，用字母代替数字），将x直接压入栈s2；
2.若x是运算符，则分情况讨论：
若x是'('，则直接压入栈s1；
若x是')'，则将距离栈s1栈顶的最近的'('之间的运算符，逐个出栈，依次压入栈s2，此时抛弃'('；
若x是除'('和')'外的运算符，则再分如下情况讨论：
若当前栈s1的栈顶元素为'('，则将x直接压入栈s1；
若当前栈s1的栈顶元素不为'('，则将x与栈s1的栈顶元素比较，若x的优先级大于栈s1栈顶运算符优先级，则将x直接压入栈s1。否者，将栈s1的栈顶运算符弹出，压入栈s2中，直到栈s1的栈顶运算符优先级别低于（不包括等于）x的优先级，或栈s2的栈顶运算符为'('，此时再则将x压入栈s1;
(3)在进行完(2)后，检查栈s1是否为空，若不为空，则将栈中元素依次弹出并压入栈s2中（不包括'#'）；
(4)完成上述步骤后，栈s2便为逆波兰式输出结果。但是栈s2应做一下逆序处理，因为此时表达式的首字符位于栈底；
转载于:https://www.cnblogs.com/luckyraye/p/6715167.html
相关资源：JAVA上百实例源码以及开源项目
