[問題描述]
一個(gè)算術(shù)表達(dá)式是由操作數(shù)(operand)、運(yùn)算符(operator)和界限符(delimiter)組成的。假設(shè)操作數(shù)是正實(shí)數(shù)，運(yùn)算符只含加減乘除等四種運(yùn)算符，界限符只含左右括號(hào)如：6+15*（21-8/4）。編程利用“運(yùn)算符優(yōu)先法”求算術(shù)表達(dá)式的值。
[基本要求]
（1）讀入一個(gè)合法的算術(shù)表達(dá)式，輸出正確的結(jié)果。
（2）考慮算法的健壯性，當(dāng)表達(dá)式錯(cuò)誤時(shí)，要給出錯(cuò)誤原因的提示。
（4）實(shí)現(xiàn)非整數(shù)的處理。
1、判斷算術(shù)表達(dá)式是否正確
2、求出運(yùn)算結(jié)果
我們平常寫出的算式對(duì)于我們來(lái)說(shuō)是比較直觀和容易計(jì)算的，這種形式的表達(dá)式被稱為中綴表達(dá)式，但對(duì)于計(jì)算機(jī)而言，中綴表達(dá)式是無(wú)法直接進(jìn)行計(jì)算的。因?yàn)樵谟?jì)算過(guò)程中，我們不是讀到一個(gè)運(yùn)算符就立即計(jì)算，而是要與后面的運(yùn)算符進(jìn)行優(yōu)先級(jí)比較，以決定先算哪個(gè)，而計(jì)算機(jī)卻做不到這點(diǎn)，但我們可以棧來(lái)解決這個(gè)問題。具體實(shí)現(xiàn)方法如下：
首先，我們創(chuàng)建兩個(gè)棧 Num 和 Sign ，Num 保存運(yùn)算數(shù)，Sign 保存運(yùn)算符號(hào)。然后，我們依次讀取表達(dá)式中的字符，若為運(yùn)算數(shù)，則轉(zhuǎn)化為對(duì)應(yīng)數(shù)值壓入?Num棧中；若為運(yùn)算符，則和 Sign棧的棧頂運(yùn)算符進(jìn)行優(yōu)先級(jí)比較：若棧頂運(yùn)算符優(yōu)先級(jí)低于當(dāng)前運(yùn)算符，則將當(dāng)前運(yùn)算符壓入Sign棧中；若棧頂運(yùn)算符優(yōu)先級(jí)高于當(dāng)前運(yùn)算符，則 Sign棧彈出運(yùn)算符、Num棧彈出兩個(gè)運(yùn)算數(shù)，進(jìn)行相應(yīng)計(jì)算，并將計(jì)算結(jié)果壓入 Num棧中；但若為 ‘)’ ，則需要將對(duì)應(yīng)左括號(hào)從 Sign棧中彈出，這就需要完成兩個(gè)括號(hào)內(nèi)的所有運(yùn)算，計(jì)算方式同上。直到表達(dá)式遍歷完畢，Num棧的棧頂元素即為最終結(jié)果。
算法思想如此，實(shí)現(xiàn)起來(lái)卻并不簡(jiǎn)單。例如，我們要將運(yùn)算數(shù)轉(zhuǎn)化為對(duì)應(yīng)數(shù)值，由于包括浮點(diǎn)數(shù)的情況，這個(gè)實(shí)現(xiàn)起來(lái)就比較復(fù)雜。以下是我的程序代碼：
# include <iostream>
# include <algorithm>
# include <string>
# include <stack>
using namespace std;
bool CheckOperator(char c); //判斷是否為運(yùn)算符
bool CheckMatch(string str); //判斷算式是否正確
int Prior(char c); //求符號(hào)的優(yōu)先級(jí)
bool CheckPrior(char c1, char c2); //通過(guò)優(yōu)先級(jí)判斷是否入棧
float CalNum(float a, float b, char c); //求單項(xiàng)運(yùn)算的結(jié)果
float CalResult(string str); //計(jì)算最終結(jié)果
int main()
{
string str;
cout << "請(qǐng)輸入計(jì)算式:";
cin >> str;
str.append("#"); //作為算式的終止符
bool t = CheckMatch(str); //判斷算式是否正確
if (t) {
float r = CalResult(str); //計(jì)算最終結(jié)果
cout << "計(jì)算結(jié)果為:" << r << endl;
}
return 0;
}
bool CheckOperator(char c) //判斷是否為運(yùn)算符
{
if (c == '+' || c == '-' || c == '*' || c == '/') {
return true;
}
else {
return false;
}
}
bool CheckMatch(string str) //判斷算式是否正確
{
if (CheckOperator(str[0]) || CheckOperator(str[str.length() - 2])) {
//算式首尾位置出現(xiàn)運(yùn)算符
cout << "算術(shù)表達(dá)式錯(cuò)誤！\n" << "原因：缺少用于運(yùn)算的數(shù)" << endl;
return false;
}
//判斷括號(hào)及運(yùn)算符輸入是否正確
stack<char>S; //用于存放括號(hào)的棧
for (int i = 0; i < str.length() - 1; i++) {
if (!CheckOperator(str[i]) && (str[i] < 48 || str[i]>57) && str[i] != '(' && str[i] != ')' && str[i] != '.') {
//出現(xiàn)非法字符
cout << "算術(shù)表達(dá)式錯(cuò)誤！\n" << "原因：出現(xiàn)非法字符" << str[i] << endl;
return false;
}
if (CheckOperator(str[i]) && CheckOperator(str[i + 1])) {
//運(yùn)算符重復(fù)
cout << "算術(shù)表達(dá)式錯(cuò)誤！\n" << "原因：運(yùn)算符" << str[i] << "重復(fù)" << endl;
return false;
}
if (str[i] == '(')
{
S.push(str[i]);
if (CheckOperator(str[i + 1])) {
//'('后缺少用于運(yùn)算的數(shù)
cout << "算術(shù)表達(dá)式錯(cuò)誤！\n" << "原因：缺少用于運(yùn)算的數(shù)" << endl;
return false;
}
}
if (str[i] == ')')
{
if (S.empty()) {
//若棧已為空，說(shuō)明遺漏左括號(hào)
cout << "算術(shù)表達(dá)式錯(cuò)誤！\n" << "原因：遺漏左括號(hào)" << endl;
return false;
}
S.pop();
}
}
if (!S.empty()) {
//若此時(shí)棧還不為空，說(shuō)明遺漏右括號(hào)
cout << "算術(shù)表達(dá)式錯(cuò)誤！\n" << "原因：遺漏右括號(hào)" << endl;
return false;
}
return true;
}
int Prior(char c) //返回符號(hào)的優(yōu)先級(jí)
{
switch (c)
{
case '#': return 0;
case '+':
case '-': return 1;
case '*':
case '/': return 2;
case ')': return 3;
case '(': return 4;
}
}
bool CheckPrior(char c1, char c2) //通過(guò)優(yōu)先級(jí)判斷是否入棧（c1當(dāng)前，c2棧中）
{
if (c2 == '(') {
return true; //同意進(jìn)棧
}
int p1 = Prior(c1);
int p2 = Prior(c2);
if (p1 > p2) { //當(dāng)前運(yùn)算符的優(yōu)先級(jí)較高
return true; //同意進(jìn)棧
}
else {
return false; //不同意進(jìn)棧
}
}
float CalNum(float a, float b, char c) //求單項(xiàng)運(yùn)算的結(jié)果
{
switch (c)
{
case '+': return a + b;
case '-': return a - b;
case '*': return a * b;
case '/': return a / b;
}
}
float CalResult(string str) //計(jì)算最終結(jié)果
{
stack<float>Num; //保存運(yùn)算數(shù)的棧
stack<char>Sign; //保存運(yùn)算符的棧
Sign.push('#');
float a, b;
for (int i = 0; i < str.length() && !Sign.empty(); i++) {
if (str[i] >= 48 && str[i] <= 57) {
//若為數(shù)字
a = float(str[i]) - 48; //a保存由字符轉(zhuǎn)化為數(shù)字后的值
int j;
//將字符轉(zhuǎn)化為數(shù)字
for (j = i + 1; (str[j] == '.') || (j < str.length() && str[j] >= 48 && str[j] <= 57); j++) {
if (str[j] == '.') {
//若為小數(shù)
int k, l;
for (k = j + 1, l = 1; k < str.length() && str[k] >= 48 && str[k] <= 57; k++, l++) {
b = float(str[k]) - 48;
a = a + b * pow(10, -l);
}
j = k;
break;
}
else {
b = float(str[j]) - 48;
a = a * 10 + b;
}
}
i = j - 1;
Num.push(a); //運(yùn)算數(shù)進(jìn)棧
}
else {
//若為運(yùn)算符
char c1 = str[i]; //c1當(dāng)前運(yùn)算符
while (1) {
char c2 = Sign.top(); //c2棧頂運(yùn)算符
if (c2 == '#' && str[i] == '#') { //若遇到起始符，并且str也到達(dá)末尾
Sign.pop();
break;
}
bool t = CheckPrior(c1, c2); //通過(guò)優(yōu)先級(jí)判斷是否入棧（c1當(dāng)前，c2棧中）
if (t) {
//同意運(yùn)算符進(jìn)棧
int s = Prior(str[i]);
if (s == 3) {
//出現(xiàn)')'，優(yōu)先進(jìn)行括號(hào)內(nèi)的運(yùn)算
while ((c2 = Sign.top()) != '(') {
a = Num.top(); //取出第一個(gè)數(shù)
Num.pop();
b = Num.top(); //取出第二個(gè)數(shù)
Num.pop();
float r = CalNum(b, a, c2); //求單項(xiàng)運(yùn)算的結(jié)果
Sign.pop();
Num.push(r); //運(yùn)算得到的新數(shù)進(jìn)棧
}
Sign.pop();
}
else {
Sign.push(c1); //運(yùn)算符進(jìn)棧
}
break;
}
else {
//不同意運(yùn)算符進(jìn)棧，執(zhí)行運(yùn)算操作
a = Num.top();
Num.pop();
b = Num.top();
Num.pop();
float r = CalNum(b, a, c2); //求單項(xiàng)運(yùn)算的結(jié)果
Sign.pop();
Num.push(r);
}
}
}
}
return Num.top();
}
?運(yùn)行結(jié)果：
請(qǐng)輸入計(jì)算式:((1+2*3)-1)/2+1.5*3
計(jì)算結(jié)果為:7.5請(qǐng)輸入計(jì)算式:(1+3)*4)-2
算術(shù)表達(dá)式錯(cuò)誤！
原因：遺漏左括號(hào)總結(jié)：實(shí)現(xiàn)簡(jiǎn)易計(jì)算器主要運(yùn)用了棧的數(shù)據(jù)結(jié)構(gòu)。其中主要的操作是通過(guò)遍歷算數(shù)表達(dá)式實(shí)現(xiàn)的，所以程序總的時(shí)間復(fù)雜度約為O(n)，n是指算數(shù)表達(dá)式的長(zhǎng)度。對(duì)于正在練習(xí)棧的小伙伴們來(lái)說(shuō)，簡(jiǎn)易計(jì)算器是很不錯(cuò)的練習(xí)項(xiàng)目。文章來(lái)源：http://www.zghlxwxcb.cn/news/detail-718742.html
以上是我個(gè)人的學(xué)習(xí)成果，很高興能與大家分享。文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-718742.html
到了這里，關(guān)于簡(jiǎn)易計(jì)算器（詳解用棧實(shí)現(xiàn)算術(shù)表達(dá)式求值）的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
