數(shù)據(jù)結(jié)構(gòu)（四）：棧的應(yīng)用之表達(dá)式求值
標(biāo)簽：
數(shù)據(jù)結(jié)構(gòu)
1、表达式求值
问题描述：
用户从控制台输入一个数学表达式（所有输入均合法），数学表达式只包含四则运算，程序需输出表达式对应的结果，如：
输入：(1+2)*3+4-5
输出：8
解题思路：
涉及到的数学符号有 +、-、*、/、(、)。
因为左边的 + 比右边的 + 优先级要高，所以我们在判断符号优先级的时候还要带上方向。
带上方向的符号优先级表为（0表示相等，1表示左边比右边大，-1表示小）：
| 横右竖左 | + | - | * | / | （ | ） |
|---|---|---|---|---|---|---|
| + | 1 | 1 | -1 | -1 | -1 | 1 |
| - | 1 | 1 | -1 | -1 | -1 | 1 |
| * | 1 | 1 | 1 | 1 | -1 | 1 |
| / | 1 | 1 | 1 | 1 | -1 | 1 |
| （ | -1 | -1 | -1 | -1 | 0 | 0 |
| ） | 1 | 1 | 1 | 1 | 0 | 0 |
两个相同优先级的符号总是左边的优先级比右边的高。
初始化两个栈，一个用来保存操作数，另一个用来保存操作符。
从控制台读取一个字符。
如果是操作数则压入操作数栈中。
如果是操作符，与操作符栈栈顶元素比较
若优先级高于栈顶元素，压入操作符栈
否则取出操作符栈栈顶元素和操作数栈栈顶的两个元素进行运算，并将运算结果压入操作数栈中。
继续执行第 4步
判断是否输入结束（遇到换行）
若输入结束，将操作符栈中的元素逐个弹出进行运算
否则继续第 2步
返回计算结果
作者：渔父歌
链接：https://www.jianshu.com/p/4add09efd981
點擊查看更多內(nèi)容
為 TA 點贊
評論
評論
共同學(xué)習(xí)，寫下你的評論
評論加載中...
作者其他優(yōu)質(zhì)文章
正在加載中
感謝您的支持，我會繼續(xù)努力的～
掃碼打賞，你說多少就多少
贊賞金額會直接到老師賬戶
支付方式
打開微信掃一掃，即可進(jìn)行掃碼打賞哦