basic calculator

文章目录

问题是求由+，-，空格，非负数，（，）组成的表达式字符串的结果是多少。

这道题目我是分两步做的，先将字符串变成逆波兰表达式，再对逆波兰表达式求解，得到结果。

将中缀式转成逆波兰表达式
用一个栈来储存符号，一个链表来储存逆波兰表达式，一个字符串来储存在遍历中缀式时遇到的数字串

从左到右遍历中缀式，遇到的字符是数字，那么就储存数字；当不是数字时，将之前的数字串塞入链表中，如果字符是(，压入符号栈；如果是+或-，弹出符号栈直到遇到(，再将当前的符号压入栈中；如果字符是），弹出符号栈直到遇到（，将这些符号塞到逆波兰表达式的最后。

最后如果符号栈中还有字符，将这些字符弹栈塞到链表后。

求解逆波兰表达式

用一个栈来储存数字

从左到右开始扫描逆波兰表达式

遇到的是数字串，那么就压栈；遇到的是符号，那么弹出两个元素，第一个弹出的是右边操作数，第二个是左边操作数，利用符号和两个操作数求出中间结果，再将中间结果压栈。重复这个过程直到遍历完逆波兰表达式，返回栈的元素就是表达式的结果。