快捷導(dǎo)航

C++表達(dá)式求值詳解

更新時(shí)間：2021年10月09日 10:10:26 作者：Computer-hacker

下面小編就為大家?guī)?lái)一篇淺談C++ 語(yǔ)言中的表達(dá)式求值。小編覺(jué)得挺不錯(cuò)的，現(xiàn)在就分享給大家，也給大家做個(gè)參考。一起跟隨小編過(guò)來(lái)看看吧

一.細(xì)節(jié)處理:

1.注意負(fù)數(shù) 因此要進(jìn)行字符串預(yù)處理

string format(string str) 
{
	int len = str.length();
	for (int i = 0; i < len; i++)
	{
		if (str[i] == '-')
		{
			if (i == 0) { str.insert(0, 1, '0'); }//處理-3*2+1情況
			else if (str[i - 1]=='(') { str.insert(i, 1, '0'); }//處理（-3*4+1）情況
		}
	}
	return str;
}

2.考慮除數(shù)為0

                    case '/':
					if (0 != y) { res = x / y; }
					else { cout << "非法表達(dá)式"; return -1; }
					break;

3.原字符串再加上一個(gè)定界符 '#'

str=str+'#'

4.優(yōu)先級(jí):

1."("未入棧前為3 入棧后為0 2.”)"和"#"為0 3.”+" "-"為1 4.”*"和"/"為2

二.知識(shí)要點(diǎn):

中綴表達(dá)式轉(zhuǎn)為后綴表達(dá)式

1. 首先設(shè)置存儲(chǔ)運(yùn)算符和存儲(chǔ)操作數(shù)兩個(gè)棧即Symbol[N]和Num[N]且分別對(duì)應(yīng)top2,top1

top1=-1 Symbol[0]='#' //運(yùn)算符棧設(shè)置定界符 top2=0

2.入棧和出棧的規(guī)則字符串為str

一.若str[i]>='0&&str[i]<='9',則入操作數(shù)棧并繼續(xù)掃描以一個(gè)字符即Num[++top1]=str[i++]-'0';

二.否則將當(dāng)前字符str1與運(yùn)算符棧的棧頂元素str2進(jìn)行優(yōu)先級(jí)比較 ,自寫(xiě)比較函數(shù)

例如: str1==‘+' 則若str2==# ,(,) 則返回1 說(shuō)明str1比str2優(yōu)先級(jí)高

1. 此時(shí)若str1優(yōu)先級(jí)大于str2 則將str1入運(yùn)算符棧并繼續(xù)掃描即 Symbol[++top2]=str[i++]

2.優(yōu)先級(jí)相等則返回0 此時(shí)將運(yùn)算符棧頂元素彈出,并繼續(xù)掃描下一個(gè)字符即 top2-- i++

3.若str1優(yōu)先級(jí)小于str2返回-1，此時(shí)將運(yùn)算符棧頂元素彈出即op=Symbol[top2--]

并彈出操作數(shù)棧的兩個(gè)元素即y=Num[top1--],x=Num[top1--] 之后進(jìn)行計(jì)算操作

三.最后 return Num[top1]

三.完整源碼:

#define _CRT_SECURE_NO_WARNINGS
#include<bits/stdc++.h>
using namespace std;
class Expression
{
public:
	Expression(string str);
	~Expression();
	int Compute();
private:
	int Comp(char str1, char str2);
	string str1;
};
Expression::Expression(string str)
{
	this->str1 = str + '#';//以定界符開(kāi)頭
}
Expression :: ~Expression() {}
//將中綴表達(dá)轉(zhuǎn)為后綴表達(dá)
int Expression::Compute()
{
	int Num[100], Symbol[100];//定義存操作數(shù)和運(yùn)算符的兩個(gè)棧
	int i, k, x, y, res;
	char op;
	Symbol[0] = '#';
	int top1 = -1, top2 = 0;
	for (i = 0; str1[i] != '\0';)
	{
		if (str1[i] >= '0' && str1[i] <= '9') { Num[++top1] = str1[i++] - '0'; }
		else {//非操作數(shù)就比較運(yùn)算符優(yōu)先級(jí)
			int cmp = Comp(str1[i], Symbol[top2]);
			if (cmp == 1) { Symbol[++top2] = str1[i++]; }//將運(yùn)算符入棧 并接著掃描下一個(gè)字符
			else if (cmp == 0) { --top2; i++; }//優(yōu)先級(jí)相等 彈棧 并接著掃描下一個(gè)字符
			else {//優(yōu)先級(jí)低 繼續(xù)處理當(dāng)前運(yùn)算符
				y = Num[top1--];//后面的數(shù)要先彈出來(lái) 才不會(huì)算反
				x= Num[top1--];
				op = Symbol[top2--];
				switch (op)
				{
				case '+':
					res = x + y;//將運(yùn)算結(jié)果入棧
					break;
				case '-':
					res = x - y;
					break;
				case '*':
					res = x * y;
					break;
				case '/':
					if (0 != y) { res = x / y; }
					else { cout << "非法表達(dá)式"; return -1; }
					break;
				default:break;
				}
				Num[++top1] = res;
			}
		}
	}
	return Num[top1]; 
}
string format(string str) 
{
	int len = str.length();
	for (int i = 0; i < len; i++)
	{
		if (str[i] == '-')
		{
			if (i == 0) { str.insert(0, 1, '0'); }//處理-3*2+1情況
			else if (str[i - 1]=='(') { str.insert(i, 1, '0'); }//處理（-3*4+1）情況
		}
	}
	return str;
}
int main()
{
	string str;
	int n = 3;
	while (n--)
	{
		cout << "請(qǐng)輸入一個(gè)表達(dá)式: " << endl;
		cin >> str;
		str = format(str);
		Expression E(str);
		int result = E.Compute();
		cout << "表達(dá)式的值的是: " << result << endl;
	}
	return 0;
}
int Expression::Comp(char str1, char str2)//當(dāng)前字符元素和棧頂運(yùn)算符優(yōu)先級(jí)比較
{
	//1代表 str1優(yōu)先級(jí)大于str2 0 代表相等 -1代表小于
	switch (str1)
	{
	case'+':case'-': 
		if (str2 == '#'||str2==')'||str2=='(') { return 1; }//左括號(hào)入隊(duì)列后優(yōu)先級(jí)變?yōu)?
		else { return -1; }
		break;
	case'*':case'/':
		if (str2 == '*' || str2 == '/') { return -1; }
		else  { return 1; }
		break;
	case'(':
		return 1;
		break;
	case')':
		if (str2 == '(') { return 0; }
		else if(str2 == '#') { return 1; }
		else { return -1; }
		break;
	case'#':
		if (str2 == '#') { return 0; }
		else { return -1; }
		break;
	default: break;
	}
}