中缀表达式转后缀表达式(PN-->RPN)
#include <stdio.h>#include <stdlib.h>
#include <ctype.h>
#define STACK_INIT_SIZE 20
#define STACKINCREAMENT 10
#define MAXBUFFER 10
typedef char ElementType;
typedef struct {
ElementType* base;
ElementType* top;
int stackSize;
}sqStack;
void InitStack(sqStack* s);
bool StackEmpty(sqStack* s);
void Push(sqStack* s, ElementType e);
void Pop(sqStack* s, ElementType* e);
bool Priority(char operator1, char operator2);
void Output(sqStack* s);
int main()
{
sqStack* s = (sqStack*)malloc(sizeof(sqStack*));
InitStack(s);
char buf;
char c, operator_stack;
c = operator_stack = '0';
double value;
while (true) {
int i = 0;
while (true) {
scanf("%c", &c);
if (isdigit(c) || c == '.') {
buf = c;
}
else if (c == ' ' && i != 0) {
buf = '\0';
value = atof(buf);
printf("%.2lf ", value);
break;
}
else {
break;
}
}
switch (c) {
case '+':
case '-':
case '*':
case '/':
while (true) {
if (StackEmpty(s)) {
Push(s, c);
break;
}
else {
Pop(s, &operator_stack);
if (Priority(c, operator_stack)) {
Push(s, operator_stack);
Push(s, c);
break;
}
else {
printf("%c ", operator_stack);
}
}
}
break;
case '(':
Push(s, c);
break;
case')':
Pop(s, &c);
while (c != '(') {
printf("%c ", c);
Pop(s, &c);
}
break;
default:
break;
}
if (c == '#') {
break;
}
}
Output(s);
}
void InitStack(sqStack* s) {
s->top = s->base = (ElementType*)malloc(STACK_INIT_SIZE * sizeof(double));
if (!s->top) {
exit(0);
}
s->stackSize = STACK_INIT_SIZE;
}
bool StackEmpty(sqStack* s) {
if (s->top == s->base) {
return true;
}
else {
return false;
}
}
void Push(sqStack* s, ElementType e) {
if (s->top - s->base >= s->stackSize) {
s->base = (ElementType*)realloc(s->base, s->stackSize + STACKINCREAMENT);
if (!s->base) {
exit(0);
}
s->stackSize = s->stackSize + STACKINCREAMENT;
}
*(s->top) = e;
s->top++;
}
void Pop(sqStack* s, ElementType * e) {
if (StackEmpty(s)) {
return;
}
*e = *--(s->top);
}
bool Priority(char operator_stackTop, char operator_ch) {
if (((operator_stackTop == '*') || (operator_stackTop == '/') || (operator_stackTop == '+') || (operator_stackTop == '-'))
&& (operator_ch == '(')) {
return true;
}
if (((operator_stackTop == '*') || (operator_stackTop == '/')) && ((operator_ch == '+') || (operator_ch == '-'))) {
return true;
}
else {
return false;
}
}
void Output(sqStack* s) {
char c;
while (s->top != s->base) {
Pop(s, &c);
printf("%c ", c);
}
}
/*
* 样例输入: 1 + 2 - 1 * ( ( 3 + 4 ) / 5 - 6 ) + 7 #
* 输出: 1 2 + 1 3 4 + 5 / 6 - * - 7 +
*/
页:
[1]