C语言 逆波兰表达式 字符串表达式计算 计算器
目录
1 起因
有个题：
链接里有个大佬写了个逆波兰表达式求解。
2 逆波兰表达式
逆波兰表达式也叫后缀表达式，依靠一个栈将字符串全部按照逆波兰表达式方式压入，在之后弹出的处理中，能够依照顺序进行计算。相应还有前缀表达式（就是波兰表达式）和中缀表达式，想法都有区别。
C语言的神器---指针。下面是稍加修改后的C语言代码：
c展开代码#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
typedef enum Type
{
NUMBER,
OPERATOR
} Type;
typedef struct Node
{
Type type;
float val;
} Node;
typedef struct Stack
{
int top;
Node *table[1000];
} Stack;
void stack_init(Stack *stack)
{
stack->top = 0;
}
void stack_push(Stack *stack, Node *pNode)
{
stack->table[stack->top++] = pNode;
}
Node *stack_pop(Stack *stack)
{
return stack->table[--stack->top];
}
Node *stack_top(Stack *stack)
{
return stack->table[stack->top - 1];
}
int stack_empty(Stack *stack)
{
return stack->top == 0;
}
Node *split(const char *s, int *length)
{
*length = 0;
int len = strlen(s);//直到碰到第一个字符串结束符'\0'为止 返回长度
Node *arr = (Node *)malloc(sizeof(Node) * len);
char digit[16];
for (int i = 0; i < len; i++)
{
if (s[i] == ' ')
continue;
if (s[i] == '+' || s[i] == '-' || s[i] == '*' || s[i] == '/' || s[i] == '(' || s[i] == ')' )
{
arr[*length].type = OPERATOR;
arr[(*length)++].val = s[i];
}
else
{
int j = 0;
while ((s[i] >= '0' && s[i] <= '9')||(s[i]=='.'))
digit[j++] = s[i++];
i--;
digit[j] = '\0';
arr[*length].type = NUMBER;
arr[(*length)++].val = strtod(digit, NULL);
}
}
return arr;
}
Node **toReversePolish(Node *arr, int *arrLength)
{
int len = *arrLength;
Stack stack;
stack_init(&stack);
Node **revPol = (Node **)malloc(sizeof(Node *) * len);
int idx = 0;
for (int i = 0; i < len; i++)
{
if (arr[i].type == NUMBER)
revPol[idx++] = &arr[i];
else if ((int)(arr[i].val) == ')')
{
*arrLength -= 2;
while (!stack_empty(&stack) && (int)(stack_top(&stack)->val) != '(')
revPol[idx++] = stack_pop(&stack);
stack_pop(&stack);
}
else if (stack.top == 0 || (int)(stack_top(&stack)->val) == '(' || (int)(arr[i].val) == '(')
stack_push(&stack, &arr[i]);
else
{
Node *op = stack_top(&stack);
if ((int)(op->val) == '+' || (int)(op->val) == '-')
{
if ((int)(arr[i].val) == '+' || (int)(arr[i].val) == '-')
{
revPol[idx++] = stack_pop(&stack);
stack_push(&stack, &arr[i]);
}
else
stack_push(&stack, &arr[i]);
}
else
{
if ((int)(arr[i].val) == '+' || (int)(arr[i].val) == '-')
{
while (!stack_empty(&stack) && (int)(stack_top(&stack)->val) != '(')
revPol[idx++] = stack_pop(&stack);
stack_push(&stack, &arr[i]);
}
else
{
revPol[idx++] = stack_pop(&stack);
stack_push(&stack, &arr[i]);
}
}
}
}
while (!stack_empty(&stack))
revPol[idx++] = stack_pop(&stack);
return revPol;
}
void printNodes(Node **nodes, int len)
{
for (int i = 0; i < len; i++)
{
if (nodes[i]->type == NUMBER)
printf("%d, ", nodes[i]->val);
else
printf("%c, ", nodes[i]->val);
}
putchar('\n');
}
float calc(Node *a, Node *b, Node *op)
{
switch ((int)(op->val))
{
case '+':
return a->val + b->val;
case '-':
return a->val - b->val;
case '*':
return a->val * b->val;
case '/':
return a->val / b->val;
}
return 0;
}
float calculate(char *s)
{
int arrLength;
Node *arr = split(s, &arrLength);
Node **revPol = toReversePolish(arr, &arrLength);
Stack stack;
stack_init(&stack);
for (int i = 0; i < arrLength; i++)
{
if (revPol[i]->type == NUMBER)
{
stack_push(&stack, revPol[i]);
}
else
{
Node *b = stack_pop(&stack);
Node *a = stack_pop(&stack);
a->val = calc(a, b, revPol[i]);
stack_push(&stack, a);
}
}
float result = stack.table[0]->val;
free(arr);
free(revPol);
return result;
}
void main()
{
printf("%.3f",calculate("12.7+((4+5/5)+1)*2+(1-4*4)"));
}
3 思路
（1）栈里top装顶点元素index+一个数组。这里的数组是一个长度为1000的结构体指针。
c展开代码typedef struct Stack
{
int top;
Node *table[1000];
} Stack;
（2）结构体。抽象叫node，node类型要么是数字类型，要么是操作符号类型。node数值是val。
如果是123，那么Type就是NUMBER，val就是123。
如果是‘+’，那么Type就是OPERATOR，val就是‘+’。
c展开代码typedef struct Node
{
Type type;
float val;
} Node;
（3）利用split将原始字符串按照结构体Node分割，全部给到Node *arr。注意，指针arr一直指向这段内存的首地址。
c展开代码Node *arr = (Node *)malloc(sizeof(Node) * len);
（4）函数toReversePolish用第三步得到的指针为参数，将整个 Node化的字符串（Node arr[]）按照逆波兰方式重新排序。、
学习指向指针的指针：https://www.runoob.com/cprogramming/c-pointer-to-pointer.html
c展开代码Node **toReversePolish(Node *arr, int *arrLength)
从前到后遍历arr，当前元素是arr[i]时候，有如下处理。
c展开代码 if (arr[i].type == NUMBER)
revPol[idx++] = &arr[i];//如果是数字就直接放入Node revPol[] 意会，其实是指向指针的指针，最后重新排序的元素内容其实是Node arr[]的一堆指针地址。
else if ((int)(arr[i].val) == ')') //逆波兰的括号处理
{
*arrLength -= 2;//回退
while (!stack_empty(&stack) && (int)(stack_top(&stack)->val) != '(')
revPol[idx++] = stack_pop(&stack);//出栈
stack_pop(&stack);//出栈
}
else if (stack.top == 0 || (int)(stack_top(&stack)->val) == '(' || (int)(arr[i].val) == '(')////逆波兰的括号处理
stack_push(&stack, &arr[i]);
else //逆波兰的运算符号
{
Node *op = stack_top(&stack);
if ((int)(op->val) == '+' || (int)(op->val) == '-')
{
if ((int)(arr[i].val) == '+' || (int)(arr[i].val) == '-')
{
revPol[idx++] = stack_pop(&stack);
stack_push(&stack, &arr[i]);
}
else
stack_push(&stack, &arr[i]);
}
else
{
if ((int)(arr[i].val) == '+' || (int)(arr[i].val) == '-')
{
while (!stack_empty(&stack) && (int)(stack_top(&stack)->val) != '(')
revPol[idx++] = stack_pop(&stack);
stack_push(&stack, &arr[i]);
}
else
{
revPol[idx++] = stack_pop(&stack);
stack_push(&stack, &arr[i]);
}
}
}
c展开代码// 1+2+3 -> 12+3+
// 1-2-3 -> 12-3-
// 1+2-3 -> 12+3-
// 1-2+3 -> 12-3+
// 1*2*3 -> 12*3*
// 1+2*3 -> 123*+
// 1*2+3 -> 12*3+
// 1/2/3 -> 12/3/
// 1*2/3 -> 12*3/
// 1+2/3 -> 123/+
// 1+2*3*4 -> 123*4*+
// 1+2+3*4*5 -> 12+34*5*+
// 1+2+3*4+5 -> 12+34*+5+
// 1+2*3*4+5 -> 123*4*+5+
// 低遇低，弹出一个，压入一个
// 低遇高，压入一个
// 高遇低，全部弹出，压入一个
// 高遇高，弹出一个，压入一个
// 遇左括，直接压入
// 遇右扩，全部弹出直到上一个左括
// (1-2)-3 -> 12-3-
// 1-(2-3) -> 123--
// (1-2)*3 -> 12-3*
// 1-(2*3) -> 123*-
// (1/2)/3 -> 12/3/
// 1*(2/3) -> 123/*
// (1+2)*((3-7)/(2+(6-7)))*(3+6) -> 12+37-*267-+/36+* OR 12+37-267-+/*36+*
作者：yu-tang-7
链接：https://leetcode-cn.com/problems/basic-calculator/solution/ni-bo-lan-biao-da-shi-jie-fa-zhi-jie-zhi-chi-by-yu/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
（5）遍历逆波兰表达式，利用一个栈对逆波兰表达式按照顺序计算。
c展开代码for (int i = 0; i < arrLength; i++)
{
if (revPol[i]->type == NUMBER)
{
stack_push(&stack, revPol[i]); //push
}
else
{
Node *b = stack_pop(&stack);//pop出1个操作数
Node *a = stack_pop(&stack);//pop出1个操作数
a->val = calc(a, b, revPol[i]);//计算pop出来的2个操作数
stack_push(&stack, a);//把计算结果push进去
}
}
如果对你有用的话，可以打赏哦
打赏
本文作者:Dong
本文链接:
版权声明:本博客所有文章除特别声明外，均采用 CC BY-NC。本作品采用《知识共享署名-非商业性使用 4.0 国际许可协议》进行许可。您可以在非商业用途下自由转载和修改，但必须注明出处并提供原作者链接。 许可协议。转载请注明出处！
目录