Infix to postfix conversion
1.operand ---> output ;
2.operator ---> 1) pop and output all operators >= precedence ; (弹出优先级大的所有操作符)
---> 2) push the operator ;
3."(" ---> push;
4.")" ---> 1)pop all oporators until "(" ; (弹出"("之上的所有操作符)
---> 2) pop the ")" without output ;
5. No more ---> pop and output all;
Postfix Calculator
1.operator ---> pop two operant off ,push result ;
2.operand ---> push on stack;
代码实现
#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
typedef struct {
char *operator;
double *operand;
int top;
int size;
}stack;
void init_stack(stack *s){
s->size = 100;
s->operator = (char*)malloc(sizeof(char) * s->size);
s->operand = (double*)malloc(sizeof(double) * s->size);
s->top = -1;//空栈
}
void free_stack(stack* s) {
if (s != NULL) {
if (s->operator != NULL) {
free(s->operator);
s->operator = NULL;
}
if (s->operand != NULL) {
free(s->operand);
s->operand = NULL;
}
s->top = -1;
}
}
int is_empty(stack* s) {
if (s->top == -1)
return 1; //为空
else
return 0; //不为空
}
int is_full(stack* s) {
if (s->top == s->size - 1)
return 1; //栈满
else
return 0; //栈未满
}
void push_stackR(stack* s, char op) {
if (is_full(s)) {
printf("\nThe stack is full!\n");
}
else {
s->top++;
s->operator[s->top] = op;
}
}
char pop_stackR(stack* s) {
if (is_empty(s)) {
printf("\nThe stack is empty!\n");
exit(1); //退出程序
}
else {
s->top--;
return s->operator[s->top + 1];
}
}
void push_stackD(stack* s, double op) {
if (is_full(s)) {
printf("\nThe stack is full!\n");
}
else {
s->top++;
s->operand[s->top] = op;
}
}
double pop_stackD(stack* s) {
if (is_empty(s)) {
printf("\nThe stack is empty!\n");
}
else {
s->top--;
return s->operand[s->top + 1];
}
}
char top_stack(stack* s) {
if (is_empty(s)) {
printf("The stack is empty!\n");
}
else {
return s->operator[s->top]; //返回栈顶元素
}
}
double top_stackD(stack* s) {
if (is_empty(s)) {
printf("The stack is empty!\n");
}
else {
return s->operand[s->top]; //返回栈顶元素
}
}
int is_operator(char operator) {
switch (operator)
{
case '+':
case '-':
return 1; break;
case '*':
case '/':
return 2; break;
default:
return 0; break;
}
}
double calculate(double a, double b, char op) {
switch (op) {
case '+':
return a + b; break;
case '-':
return a - b; break;
case'*':
return a * b; break;
case '/':
return a / b; break;
default:
printf("Invalid operator!\n");
}
}
// Infix to postfix conversion
char* to_postfix(char exp[]) {
stack s;
init_stack(&s);
char pexp[100];
int i,index=0;
for (i = 0; i < strlen(exp); i++) {
// 1.operand ---> output ;
if ((exp[i] >= '0' && exp[i] <= '9') || exp[i] == '.') {
pexp[index] = exp[i];
index++;
}
// 2.operator ---> pop and output all operators >= precedence ; push the operator;
else if (is_operator(exp[i])) {
pexp[index] = ' ';
index++;
while (!is_empty(&s) && is_operator(top_stack(&s)) > is_operator(exp[i]))
{
pexp[index] = pop_stackR(&s);
index++;
pexp[index] = ' ';
index++;
}
push_stackR(&s, exp[i]);
}
// 3."(" ---> push;
else if (exp[i] == '('&&!is_full(&s)) {
push_stackR(&s, exp[i]);
}
// 4.")" ---> pop all oporators until "(" ; pop the ")" without output;
else if (exp[i] == ')') {
pexp[index] = ' ';
index++;
while (top_stack(&s) != '(') {
pexp[index] = pop_stackR(&s);
index++;
}
pop_stackR(&s);
}
}
pexp[index] = ' ';
index++;
// 5. No more ---> pop and output all;
while (!is_empty(&s)) {
pexp[index] = pop_stackR(&s);
index++;
pexp[index] = ' ';
index++;
}
pexp[index] = '\0';
free_stack(&s);
return pexp;
}
double is_digit(char* c) {
int i = 0, hasPoint = 0;
double num = 0.0, fac = 1.0;
if (c[0] < '0' || c[0] > '9') {
return 0;
}
else {
for (i = 0; i < strlen(c); i++) {
if (c[i] == '.') {
hasPoint = 1;
fac = 0.1;
}
else if (c[i] >= '0' && c[i] <= '9') {
if (hasPoint) {
num += (c[i] - '0') * fac;
fac *= 0.1;
}
else {
num = num * 10 + (c[i] - '0');
}
}
}
}
return num;
}
double postfix_calculator(char* exp) {
stack s;
init_stack(&s);
char ch[50];
double num = 0, op1 = 0, op2 = 0, result = 0;
int i, j, ch_len = 0;
for (i = 0; i < strlen(exp); i++) {
/*printf("\n------------------------------\n");
printf("exp[i]=%c , i=%d", exp[i],i);
printf("\n------------------------------\n");*/
ch_len = 0; // 重置ch的长度
if (exp[i] >= '0' && exp[i] <= '9') {
for (j = i; j < strlen(exp) && exp[j] != ' '; j++, ch_len++) {
ch[ch_len] = exp[j];
}
ch[ch_len] = '\0'; // 添加字符串终止符
i = j-1;
}
if (is_digit(ch)) {
num = is_digit(ch);
}
if (num != 0 && exp[i]==' ') {
//printf("\n********operand***********\n");
push_stackD(&s, num);
//printf("push_num:%.2f\n", top_stackD(&s));
num = 0;
}
else if (is_operator(exp[i])) {
//printf("\n########operator#########\n");
num = 0;
op2 = pop_stackD(&s);
op1 = pop_stackD(&s);
//printf("%.2f %.2f %c\n", op1, op2, exp[i]);
result = calculate(op1, op2, exp[i]);
//printf("result:%.2f\n", result);
push_stackD(&s, result);
i++;
}
}
result = top_stackD(&s);
free_stack(&s);
return result;
}
void test() {
char exp[100], * pexp, pexp1[100];
double result = 0, result2 = 0, result1 = 0;
printf("请输入表达式:");
scanf("%s",exp);
pexp = to_postfix(exp);
printf("\n该表达式的后缀形式为:%s\n", pexp);
strcpy(pexp1, pexp);
result = postfix_calculator(pexp1);
printf("该表达式的结果为:%.2f\n", result);
}
int main() {
test();
return 0;
}
// 3+2*(3-1.5)-5/2 3.5
// 5+15*(4.5-(7/2))-6*(3/2) 11
结果展示
参考资料
http://t.csdnimg.cn/BeRHx 【栈(stack) C语言实现 详解】
http://t.csdnimg.cn/pNxPS 【C语言实现栈(Stack)数据结构】
http://t.csdnimg.cn/GCcH3 【四则运算表达式求值(支持括号、负数)】
标签:index,优先级,top,pop,stack,----,operator,return,Stack From: https://blog.csdn.net/m0_74219898/article/details/139294104